月度归档： 2020 年 6 月

问题

思路

代码

#include "pch.h"
#include 
struct Point{
	int x;
	int y;
};

int main()
{
	int max_x = 0, max_y = 0;
	int maze_arr[100][100] = { 0 };
	scanf("%d %d", &max_x, &max_y);

	if (max_x * max_y <= 0) {
		printf("Wrong input!\n");
		return 0;
	}

	if (max_x * max_y == 1) {
		printf("No solution!\n");
		return 0;
	}

	for (int i = 0; i < max_x; i++) {
		for (int j = 0; j < max_y; j++) {
			scanf("%d", &maze_arr[i][j]);
		}
	}
	
	printf("\n");
	//第一个参数是控制行,第二个参数才是控制列
	

	int x = 0, y = 0;
	int k = 0;//步数索引
	int round = 0;

	Point path[100];//路径
	int flag[100][100];//是否走过
	int dir[100] = { 0 }; //搜索方向
	Point delta[4];//偏移量
	flag[0][0] = 1;
	while (true) {
		//0,0 第一列第0行
		//左边 0,-1 第0行第1列
		//右边 0,1 第0行第1列
		//上边 -1,0 第-1行第0列
		//下边 1,0 第1行第0列
		round = 0;//重置遍历次数
		//左方 0
		delta[0].x = x;
		delta[0].y = y - 1;
		//上方 1
		delta[1].x = x - 1;
		delta[1].y = y;
		//右方 2
		delta[2].x = x;
		delta[2].y = y + 1;
		//下方 3
		delta[3].x = x + 1;
		delta[3].y = y;
		for (int i = 0; i < 4; i++) {
			//不超出迷宫边界，即不小于0，不大于行/列
			if (delta[i].x >= 0 && delta[i].y >= 0 && delta[i].x < max_x && delta[i].y < max_y) {
				//不是墙，即所在格子值不为1
				
				if (maze_arr[delta[i].x][delta[i].y] != 1) {
					//没走过，即所在格子的flag值不为1
					if (flag[delta[i].x][delta[i].y] != 1) {
						
						//将偏移量delta加到当前坐标上
						x = delta[i].x;
						y = delta[i].y;
						path[k].x = x;
						path[k].y = y;
						//记录当前的搜索方向dir
						dir[k] = i;
						k++;
						//将当前位置的flag值标为1，表示已走
						flag[x][y] = 1;
						//是否最后一步
						if (x == max_x - 1 && y == max_y - 1) {
							//输出坐标
							printf("<0,0>\n");
							for (int j = 0; j < 100; j++) {
									if (path[j].x >= 0) {
										printf("<%d,%d>\n", path[j].x, path[j].y);
									}
							}
							return 0;
						}
						break;
					}
				}
			}
			round++;
		}
		
		if (round == 4) {
			//将当前坐标的搜索方向dir重置为0
			dir[k] = 0;
			path[k].x = 0;
			path[k].y = 0;
			//将当前坐标回退到上一步
			
			switch (dir[k-1]) {
			case 0:
				y++;
				break;
			case 1:
				x++;
				break;
			case 2:
				y--;
				break;
			case 3:
				x--;
				break;
			}
			if (k - 1 < 0) {
				printf("No solution!\n");
				break;
			}
			//令上一步的搜索方向加1（不然会重复上一次的方向）
			dir[k - 1]++;
			//回退到上一步，即让k减1
			k--;
		}

	}
	return 0;
}

运行截图

来源

华南理工大学广州学院 – 林煜东 linyd@gcu.edu.com