定义一个二维数组:
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)
记录路径并输出
代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7 struct shu
8 {
9 int y,x,step;
10 }str1,str2;
11 int a,s,d,f,g,q[10][10],v[10][10],w[10][10],z[25],c[25];
12 int p[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
13 void bfs()
14 {
15 int xx,yy,x,y;
16 queue<shu>r;
17 r.push(str1);
18 while(!r.empty())
19 {
20 str1=r.front();
21 r.pop();
22 if(str1.y==4 && str1.x==4)
23 {
24 xx=q[str1.y][str1.x]%10;
25 yy=(q[str1.y][str1.x]-xx)/10;
26 while(1) //while循环找寻路径
27 {
28 z[g]=yy;c[g]=xx;
29 g++;
30 if(q[yy][xx]==0)
31 {
32 break;
33 }
34 x=q[yy][xx]%10; //找到这一个点的前一个点的坐标(因为我们之前维护过,所以用同样方式找寻点坐标)
35 y=(q[yy][xx]%100-x)/10;
36 yy=y;
37 xx=x;
38 }
39 while(!r.empty())
40 r.pop();
41 return;
42 }
43 str2.step=str1.step+1;
44 for(int i=0;i<4;++i)
45 {
46
47 str2.y=str1.y+p[i][1];
48 str2.x=str1.x+p[i][0];
49 if(str2.y<0 || str2.x<0 || str2.y>=5 || str2.x>=5) continue;
50 if(v[str2.y][str2.x]==0 && w[str2.y][str2.x]==0)
51 {
52 q[str2.y][str2.x]=str1.y*10+str1.x; //把它的前一个点的坐标维护成一个唯一值
53 w[str2.y][str2.x]=1;
54 r.push(str2);
55 /*
56 除了这一种方式之外,我们还可以定义一个结构体专门保存上一个点的坐标
57
58 */
59 }
60 }
61 }
62 }
63 int main()
64 {
65 g=0;
66 for(int i=0; i<5;++i)
67 {
68 for(int j=0; j<5 ;++j)
69 {
70 scanf("%d",&v[i][j]);
71 }
72 }
73 q[0][0]=0;
74 str1.x=0;
75 str1.y=0;
76 str1.step=0;
77 w[0][0]=1;
78 bfs();
79 printf("(0, 0)\n");
80 for(int i=g-1;i>=0;--i)
81 {
82 printf("(%d, %d)\n",z[i],c[i]);
83 }
84 printf("(4, 4)\n");
85 return 0;
86 }