迷宫问题 POJ - 3984 ( 搜索最短路记录路径）-白红宇

迷宫问题 POJ - 3984 ( 搜索最短路记录路径）

阅读量：4046 次

发布时间：2019-05-25

本文共 1386 字，大约阅读时间需要 4 分钟。

定义一个二维数组：

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)

题意：

给出一个5*5的地图，找到从（0,0）点到达（4,4）点的最短路径，输出路径

首先想到的就是广搜，并且每找到一个符合的点时，都要记录下来前面的那个点。

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int map[7][7];   //记录地图struct node{	int x,y;   //每一点的(x,y)	int step;  //走过的步数	int pre;   //存储这个点的前一步 };int nex[4][2]={
  {1,0},{-1,0},{0,1},{0,-1}};struct node q[10000];  //用数组来代替队列int l,r;          //l表示头坐标，r代表尾坐标，头坐标出队，尾坐标入队int vis[7][7];    //记录走过的点int path[10000];  //存储路径void Print(){   	int k=0;   	while(l!=0)  //找到走过的路径，l为0是起始点   	{   	   	path[k]=q[l].pre; //不断地找前一个点   	   	k++;   	   	l=q[l].pre;	}	for(int i=k-1;i>=0;i--)	{		printf("(%d, %d)\n",q[path[i]].x,q[path[i]].y);	}		cout<<"(4, 4)"<
       
        =0&&ty>=0&&tx<=4&&ty<=4&&vis[tx][ty]==0&&map[tx][ty]==0)			{				vis[tx][ty]=1; //标记走过的点				q[r].x=tx;     //符合条件的点入队				q[r].y=ty;				q[r].pre=l;				q[r].step=nod.step+1;				r++;			}		}		l++;  //首元素出队	}}int main(){	for(int i=0;i<5;i++)	{		for(int j=0;j<5;j++)		{			scanf("%d",&map[i][j]);		}	}	bfs();	return 0;}