poj 3984迷宫问题（bfs求最短路径类似并查集保存上个节点保存最短路径）-白红宇

poj 3984迷宫问题（bfs求最短路径类似并查集保存上个节点保存最短路径）

阅读量：4048 次

发布时间：2019-05-25

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

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16343		Accepted: 9762

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 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)

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int k=0;int pre[30];int map[7][7];int vis[7][7];int dx[]={	0,0,-1,1};int dy[]={	1,-1,0,0};void pp(){	int a[30];	int u=24;	int t=0;	while(1)	{		a[t++]=pre[u];//找到路径 当回到起点时退出 		u=pre[u];		if(u==0)		break;	}		for(int i=t-1;i>=0;i--)	{		printf("(%d, %d)\n",a[i]/5,a[i]%5);//余数表示y坐标 整除部分表示x坐标 	}	printf("(4, 4)\n");	return ;}typedef pair
        
          pa;void bfs(int p,int q){ queue
         
           que; vis[p][q]=1; que.push(pa(p,q)); while(!que.empty()) { pa now=que.front(); que.pop(); int x=now.first; int y=now.second; for(int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(xx<0||xx>=5||yy<0||yy>=5||vis[xx][yy]==1||map[xx][yy]==1) continue; else{ pre[5*xx+yy]=5*x+y;//模仿并查集 保存父节点 从终点开始往回追溯 if(xx==4&&yy==4) { pp(); return; } vis[xx][yy]=1; que.push(pa(xx,yy)); } } } return ;}int main(){ memset(vis,0,sizeof(vis)); for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { scanf("%d",&map[i][j]); } } bfs(0,0); return 0;}