迷宫问题 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9112 Accepted: 5392 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 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)
#include<iostream>
#include<queue>
#include<list>
#include<iterator>
#define Min 0xfffffff
using namespace std;
int ansx[20],ansy[20],map[20][20];//用于看是否记录是否到达过
int minn = Min;
int dx[4] = {0,1,-1,0};
int dy[4] = {1,0,0,-1};
//右 下 上 左
struct s
{
int x,y;
int step;
}a,temp,pre[20][20];//pre数组用于记录由哪个位置到达
int check(s temp)//判定条件
{
if(temp.x < 0||temp.x >4||temp.y > 4 || temp.y <0||map[temp.x][temp.y])
{
return 0;
}
return 1;
}
void bfs()
{
queue<struct s> q;
a.x = 0;
a.y = 0;
a.step = 0;
map[a.x][a.y] = 1;
q.push(a);
while(!q.empty())
{
a = q.front();
temp = a;//为了得到步数
q.pop();
for(int i = 0; i < 4; i++)
{
temp.x = a.x+dx[i];
temp.y = a.y+dy[i];
temp.step = a.step+1;
if(check(temp))
{
if(temp.x==4&&temp.y==4)
{
if(temp.step < minn)
{
minn = temp.step;
pre[temp.x][temp.y].x= a.x;
pre[temp.x][temp.y].y = a.y;
}
continue;//为了不让终点被标记
}
pre[temp.x][temp.y].x = a.x;
pre[temp.x][temp.y].y = a.y;
map[temp.x][temp.y] = 1;
q.push(temp);
}
}
}
}
int main()
{
int i,j;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
scanf("%d",&map[i][j]);
}
bfs();
list<s> li;
list<s>::iterator it;
int x = 4, y = 4,xt,yt;
do
{
li.push_back(pre[x][y]);
xt = pre[x][y].x;
yt = pre[x][y].y;
x = xt;
y = yt;
}
while(pre[x][y].x!=0&&pre[x][y].y!=0);
li.push_back(pre[x][y]);
li.reverse();
cout << "<0,0>"<<endl;
for(it = li.begin();it!=li.end(); it++)
{
cout <<"("<< (*it).x <<","<< (*it).y<<")"<<endl;
}
cout << "<4,4>"<<endl;
cout << minn;
return 0;
}