来源: http://poj.org/problem?id=3984
迷宫问题
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8154 | Accepted: 4804 |
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)
Source
题意:略
题解:
非常基础的题，没有挖坑。
三种方法解决之
1.递归DFS+回溯
2.非递归DFS+回溯
3.BFS
2.非递归DFS+回溯
3.BFS
//前两种方法均是先将全部路径求出再找出最短路径~~ 第三种方法BFS，不用说了，肯定是最短的。
PS: poj这题的測试数据真的是好弱好弱！
！。 開始交了两个考虑不到位的代码也给过了...
AC代码1:
/*
MummyDing
POJ 3984迷宫问题【DFS】
*/
#include<iostream>
#define Max 100
using namespace std;
int maze[5][5],road[25][2]={0},temproad[25][2],pos=0;
int dir[4][2]={
{1,0},{0,1},{-1,0},{0,-1} //四个方向
};
struct Road{
int r[30][2],step; //用于存储路径
}roads[Max];
void dfs(int x,int y,int step){
if(x==4&&y==4){ //达到目标状态
roads[pos].step=step;
for(int i=1;i<step;i++){
roads[pos].r[i][0]=temproad[i][0];
roads[pos].r[i][1]=temproad[i][1];
}
pos++;
return ;
}
for(int i=0;i<4;i++){ //四个方向进行搜索
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=0&&dy>=0&&dx<5&&dy<5&&!maze[dx][dy]){
maze[dx][dy]=1;
temproad[step][0]=dx; temproad[step][1]=dy;
dfs(dx,dy,step+1); //DFS+回溯
maze[dx][dy]=0;
}
}
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>maze[i][j]; //输入数据
dfs(0,0,1); //dfs，找出全部路径
int ans=0; //找出最短路径
for(int i=1;i<pos;i++)
if(roads[i].step<roads[ans].step)
ans=i;
for(int i=0;i<roads[ans].step;i++)
cout<<'('<<roads[ans].r[i][0]<<", "<<roads[ans].r[i][1]<<')'<<endl;
return 0;
}AC代码2:
/*
MummyDing
POJ3984迷宫问题【非递归】
*/
#include<iostream>
#include<cstring>
#define Max 100
using namespace std;
struct Node{
int maze[5][5]; //x,y 代表当前位置
int x,y,exdir[4],step; // exdir标记该方向之前是否被走过
}stack[Max]={0},temp={0};
struct Road{
int r[30][2],step;
}roads[Max];
int top=0,pos=0;
int dir[4][2]={
{0,1},{1,0},
{-1,0},{0,-1}
};
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>stack[0].maze[i][j];
while(~top)
{
if(stack[top].x==4&&stack[top].y==4) //达到目标状态
{
roads[pos].step=stack[top].step;
for(int i=0;i<=stack[top].step;i++)
{
roads[pos].r[i][0]=stack[i].x;
roads[pos].r[i][1]=stack[i].y;
}
pos++;
}
bool flag=true;
for(int i=0;i<4;i++)
{
temp=stack[top];
int dx=dir[i][0]+temp.x,dy=dir[i][1]+temp.y;
if(dx>=0&&dy>=0&&dx<5&&dy<5&&!temp.maze[dx][dy]&&!temp.exdir[i]){
stack[top].exdir[i]=1;//标记此方向
temp.maze[temp.x][temp.y]=1; //标记走过的点
temp.x=dx;temp.y=dy; //状态转移到该节点
temp.step++; //步数加1
stack[++top]=temp; //结点入栈
memset(stack[top].exdir,0,sizeof(stack[top].exdir));
flag=false;
break;
}
}
if(flag)
top--;
}
int ans=0;
for(int i=1;i<pos;i++)
if(roads[i].step<roads[ans].step)
ans=i;
for(int i=0;i<=roads[ans].step;i++)
cout<<'('<<roads[ans].r[i][0]<<", "<<roads[ans].r[i][1]<<')'<<endl;
return 0;
}
/*
測试数据
0 1 0 0 0
0 0 0 1 0
1 0 1 1 0
1 0 0 0 0
1 1 1 1 0
*/AC代码3:
/*
MummyDing
POJ 3984迷宫问题BFS
*/
#include<iostream>
#include<cstring>
#define Max 500
using namespace std;
struct Node{
int maze[5][5];
int x,y,step,pre; //pre用来记录上个节点的位置
}map[Max]={0},temp={0};
int road[30][2], exdir=0,nodedir=0;
int dir[4][2]={
{0,1},{1,0},{-1,0},{0,-1}
};
bool equal(Node x,Node y)
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(x.maze[i][j]^y.maze[i][j]) return false;
return true;
}
bool check(Node x) //判重
{
for(int k=0;k<exdir;k++)
if(equal(x,map[k])) return false;
return true;
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>map[0].maze[i][j];
map[0].pre=-1;
while(nodedir<=exdir&&exdir<Max)
{
for(int i=0;i<4;i++) //四个方向进行搜索
{
temp=map[nodedir];// 头结点
temp.pre=nodedir; temp.maze[temp.x][temp.y]=1; //做标记
temp.x+=dir[i][0]; temp.y+=dir[i][1]; temp.step++;
if(temp.x<5&&temp.y<5&&temp.x>=0&&temp.y>=0&&!temp.maze[temp.x][temp.y])
{
if(temp.x==4&&temp.y==4)
{
int k=temp.step; int m=k;
road[k][0]=temp.x;road[k--][1]=temp.y;
for(;k>0;k--){
road[k][0]=map[temp.pre].x;
road[k][1]=map[temp.pre].y;
temp=map[temp.pre];
}
for(int k=0;k<=m;k++)
cout<<'('<<road[k][0]<<", "<<road[k][1]<<')'<<endl;
return 0;
}
else if(check(temp)) //该节点没有就加到队列中
map[++exdir]=temp;
}
}
nodedir++;
}
return 0;
}
/*
0 1 0 0 0
0 0 0 1 0
1 0 1 1 0
1 0 0 0 0
1 1 1 1 0
*/