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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

 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 }