问题
思路
代码
#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
