【原】7-1 迷宫寻路 (20分)

文章目录

7-1 迷宫寻路 (20分)

给定一个M行N列的迷宫图，其中 "0"表示可通路，"1"表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。

5行8列的迷宫如下：

0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0

则从左上角（1，1）至右下角（5，8）的最短路径为：

1,1–》2,1–》2,2–》2,3–》3,3–》3,4–》3,5–》4,5–》5,5–》5,6–》5,7–》5,8

题目保证每个迷宫最多只有一条最短路径。

请输出该条最短路径，如果不存在任何通路，则输出"NO FOUND".

输入格式:

第一行，输入M和N值，表示迷宫行数和列数。

接着输入M行数值，其中，0表示通路，1表示障碍物。每列数值用空格符间隔。

接下来可能输入多组迷宫数据。

当输入M的值为-1时结束输入。

输出格式:

按行顺序输出路径的每个位置的行数和列数，如 x,y

如果不存在任何路径，则输出"NO FOUND".

每组迷宫寻路结果用换行符间隔。

输入样例:

在这里给出一组迷宫。例如：

8 8    
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4    
0 0 1 0
0 0 0 0
0 0 1 1 
0 1 0 0
-1 -1

输出样例:

在这里给出相应的输出。例如：

1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8

NO FOUND

题解

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

int n, m, Min;// Min 最短路径全局变量 n行m列
int Map[100][100];// 记录整个地图  0 1 标记
int vis[100][100];// 记录当前走过的地图
int dir[4][2] = { 0,1,
0,-1,
-1,0,
1,0 };// 方向
int stepA[100][2];// 记录当前走的路径坐标
int stepB[100][2];// 记录最短走过的路径坐标

// 进行深度优先搜索
void dfs(int x, int y, int step)
{
// 判断如果当前分支步数已经超了Min了 就不用继续搜索了
if (step > Min)
{
return;
}

// 当前分支步数小于当前最短步数
// 如果路径搜到终点  就把当前的step赋值给Min，路径存入stepB
if (x == n && y == m)
{
for (int i = 0; i < 100; ++i)
{
if (stepA[i][0] == -1 && stepA[i][1] == -1)
{
break;
}
stepB[i][0] = stepA[i][0];
stepB[i][1] = stepA[i][1];
}
Min = step;
return;
}

// 像四个方向继续搜索
for (int i = 0; i < 4; ++i)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];

if (xx <= 0 || yy <= 0 || xx > n || yy > m)
{
// 出界了就进行下一个
continue;
}
if (!vis[xx][yy] && Map[xx][yy] == 0)
{
stepA[step][0] = xx;
stepA[step][1] = yy;

vis[xx][yy] = 1;
dfs(xx, yy, step + 1);
vis[xx][yy] = 0;
}
}
return;
}

int main()
{
while (scanf("%d %d", &n, &m) && m != -1)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
scanf("%d", &Map[i][j]);
}
}
// 初始化数据
memset(vis, 0, sizeof(vis));
memset(stepA, -1, sizeof(stepA));
memset(stepB, -1, sizeof(stepB));

vis[1][1] = 1;

Min = 10000;// 赋初值
dfs(1, 1, 0);// 深度优先遍历
if (Min == 10000)
{
printf("NO FOUND\n");
}
else
{
printf("1,1\n");
for (int i = 0; i < Min; i++)
{
printf("%d,%d\n", stepB[i][0], stepB[i][1]);
}
printf("\n");
}
}

return 0;
}