转自：

 

定义一个二维数组： 

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 00 1 0 1 00 0 0 0 00 1 1 1 00 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
     
       2 using namespace std; 3 int map[5][5]; 4 int vis[5][5]; 5 struct node{ 6     int x; 7     int y; 8     int pre; 9 }edge[100];10 int front=0,rear=1;//队头，队尾11 int dir[4][2]={
   {
   0,-1},{
   1,0},{
   0,1},{-1,0}};12 void f(int i)//倒向追踪法13 {14     if(edge[i].pre!=-1)15     {16         f(edge[i].pre);17         cout<<"("<
      
       <<", "<
       
        <<")"<
        
         =5||y<0||y>=5||vis[x][y]==1||map[x][y]==1)33                 continue;34             else35             {36                 vis[x][y]=1;37                 map[x][y]=1;38                 edge[rear].x=x;//入队39                 edge[rear].y=y;40                 edge[rear].pre=front;41                 rear++;42             }43             if(x==4&&y==4)44                 f(front);45         }46         front++;//出队47     }48 }49 int main()50 {51     int i,j;52     for(i=0;i<5;i++)53     {54         for(j=0;j<5;j++)55         {56             cin>>map[i][j];57         }58     }59     memset(vis,0,sizeof(vis));60     cout<<"("<<"0, 0)"<