Description
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走
的路，只能横着走或竖着走，不能斜着走，要求编
程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
#include <cstdio>
#include <iostream>
#include <cmath>
#include <
string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
int f[
8][
8], ii =
0;
struct node
{
int x, y;
};
struct edge
//记录每个点
{
int x, y;
}e[8][
8];
int path[
4][
2] = {
0,
1,
0,-
1,
1,
0, -
1,
0};
void bfs()
{
queue<node>
q;
node p;
p.x =
0;
p.y =
0;
q.push(p);
while(!
q.empty())
{
node l =
q.front();
q.pop();
if(l.x ==
4 && l.y ==
4)
return;
for(
int i =
0; i<
4; i++
)
{
node w;
w.x = l.x+path[i][
0];
w.y = l.y+path[i][
1];
if(w.x >=
0 && w.y >=
0 && w.x<
5 && w.y<
5 && !
f[w.x][w.y])
{
f[w.x][w.y] =
1;
e[w.x][w.y].x = l.x;
//记录该点的上一个点，因为上一个点是确认的
e[w.x][w.y].y = l.y;
//记录该点的上一个点，因为上一个点是确认的
q.push(w);
}
}
}
}
void print(
int a,
int b)
{
if(a ==
0 && b ==
0)
{
printf("(0, 0)\n");
return;
}
print(e[a][b].x, e[a][b].y);
printf("(%d, %d)\n", a, b);
}
int main()
{
for(
int i =
0; i<
5; i++
)
for(
int j =
0; j<
5; j++
)
scanf("%d", &
f[i][j]);
f[0][
0] =
1;
bfs();
print(4,
4);
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10890943.html
相关资源：JAVA上百实例源码以及开源项目
