首页 > 代码库 > POJ 3984 迷宫问题
POJ 3984 迷宫问题
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)
AC代码：
#include<stdio.h>char maze[6][6];struct change{ int x,y,front;}turn[100],next;//建立队列int head,tail;int move[4][2]={1,0,0,1,-1,0,0,-1};//移动void showstep()//输出最短路径{ int a[100],i; a[0]=tail; for(i=1;turn[a[i-1]].front!=-1;i++)//{ // printf("%d %d\n",turn[a[i-1]].x,turn[a[i-1]].y); a[i]=turn[a[i-1]].front; //} for(i=i-1;i>=0;i--) printf("(%d, %d)\n",turn[a[i]].x,turn[a[i]].y); return;}void BFS()//搜索{ turn[0].x=0; turn[0].y=0; turn[0].front=-1; maze[0][0]=1; int i; head=-1; while(tail>head){ //for(i=0;i<5;i++) // for(int j=0;j<5;j++){ // printf("%d",maze[i][j]); // if(j==4) // printf(" "); //} //printf("%d\n%d\n",head,tail); head++; for(i=0;i<4;i++){ next.x=turn[head].x+move[i][0]; next.y=turn[head].y+move[i][1]; if(next.x>=0&&next.y>=0&&next.x<5&&next.y<5&&maze[next.x][next.y]==0){//搜索过程 tail++;//加队尾 maze[next.x][next.y]=1; turn[tail].x=next.x; turn[tail].y=next.y; turn[tail].front=head; if(next.x==4&&next.y==4){ showstep(); return; } } } }}int main(){ int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) scanf("%d",&maze[i][j]);//输入 BFS(); return 0;}
心得：多做题，才能体会
POJ 3984 迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。