本文主要是介绍迷宫问题 poj 3984，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目：迷宫问题
2.题意：一个5 × 5的二维数组，表示一个迷宫。0表示通路，1表示墙，输出从左上角到右下角的最短路径。
3.思路：简单bfs,递归输出路径。
4.代码：
#include<stdio.h>
#include<string.h>
int map[6][6];
int visit[25][25];
int pre[100];
int dir[4][2]= {1,0,-1,0,0,1,0-1};
struct Node
{int x,y;
} a[30];
void print(int x)
{int m=pre[x];if(m==0){printf("(0, 0)\n");printf("(%d, %d)\n",a[x].x,a[x].y);return ;}else{print(m);printf("(%d, %d)\n",a[x].x,a[x].y);}
}
void bfs()
{memset(visit,0,sizeof(visit));Node cur,change;int front=0;int rear=1;a[0].x=0;a[0].y=0;pre[0]=-1;while(front<rear){int tx,ty;cur.x=a[front].x;cur.y=a[front].y;if(cur.x==4&&cur.y==4){print(front);return ;}else{for(int i=0; i<4; i++){tx=cur.x+dir[i][0];ty=cur.y+dir[i][1];if(tx>=0&&tx<5&&ty>=0&&ty<5&&visit[tx][ty]==0&&map[tx][ty]==0){visit[tx][ty]=1;a[rear].x=tx;a[rear].y=ty;pre[rear]=front;rear++;}}front++;}}return ;
}
int main()
{int i,j;for(i=0; i<5; i++){for(j=0; j<5; j++){scanf("%d",&map[i][j]);}}bfs();return 0;
}
这篇关于迷宫问题 poj 3984的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
