迷宫问题
迷宫 问题
2023-09-27 14:23:31 时间
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 11281 | Accepted: 6745 |
Description
定义一个二维数组：
它表示一个迷宫。当中的1表示墙壁，0表示能够走的路。仅仅能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
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)提交时由于多加了一个using namespace std;导致错误。
#include<stdio.h>
#include<string.h>
int a[4]={1,-1,0,0},b[4]={0,0,-1,1};
int map[5][5];
struct stu{
int one,two;
}list[2000];
int pre[100];
int visit[10][10];
void print(int x)
{
int t;
t=pre[x];
if(t==0)
{
printf("(0, 0)\n");
printf("(%d, %d)\n",list[x].one,list[x].two);
return ;
}
else
print(t);
printf("(%d, %d)\n",list[x].one,list[x].two);
}
void bfs()
{
int i,head,tail;
int x,y,xx,yy;
memset(visit,0,sizeof(visit));
head=0;tail=1;
list[0].one=0;
list[0].two=0;
pre[0]=-1;
while(head<tail)
{
x=list[head].one;
y=list[head].two;
if(x==4&&y==4)
{
print(head);
return ;
}
for(i=0;i<4;i++)
{
xx=x+a[i];
yy=y+b[i];
if(!visit[xx][yy]&&xx>=0&&xx<5&&yy>=0&&yy<5&&map[xx][yy]==0)
{
visit[xx][yy]=1;
list[tail].one=xx;
list[tail].two=yy;
pre[tail]=head;
tail++;
}
}
head++;
}
return ;
}
int main()
{
while(1)//提交时去掉
{//
int i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&map[i][j]);
bfs();
}//
return 0;
}