poj迷宫问题

迷宫问题

题意：

定义一个二维数组：

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)

简单思路：

用广度优先搜索找出最优路线，因为本题一定有解，所以，不用去讨论解的存在性。而此题的一个特点即为，要输出这个解。因此该解的路线需要记录下来。用一个结构体node（见代码）来记录点。该结构体中除了记录坐标的点x,y还有一个pre记录其前驱。使用双端队列，因为其前驱后继都要访问。

代码如下：

#include<iostream> using namespace std; int map[5][5]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; //设置四个方向 int front=0,rear=1; //初始化头尾节点 //设置头尾节点 struct node{ int x,y,pre; }q[100]; //node的数据结构 //前驱，加上x,y的坐标值 //记录其父节点。 void print(int i) { if(q[i].pre!=-1) { print(q[i].pre); cout<<"("<<q[i].x<<", "<<q[i].y<<")"<<endl; } } //递归输出 //广搜 void bfs(int x1,int y1) { q[front].x=x1; q[front].y=y1; //设置队列的头结点 //即x1,y1; q[front].pre=-1; //初始化节点的父节点不存在 int a,b; while(front<rear) { for(int i=0;i<4;i++) { a=dx[i]+q[front].x; b=dy[i]+q[front].y; //四个方向的试探 if(a<0||a>=5||b<0||b>=5||map[a][b]) continue; else { map[a][b]=1; //记录该点已经走过即变为“墙”。 q[rear].x=a; q[rear].y=b; //尾节点记录新加进去的点 q[rear].pre=front; rear++; } if(a==4&&b==4) print(front); } //在一个试探周期结束之后 //头结点向后移一个 front++; } } int main() { int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) cin>>map[i][j]; cout<<"(0, 0)"<<endl; bfs(0, 0); cout<<"(4, 4)"<<endl; return 0; }

以上是标准答案

下面是弱鸡作者的代码

该代码一直WA，希望哪个大佬看见能随手指导一下

但是本人认为思路应该是对的。

#include <iostream> #include<cstring> #include<queue> #include<stack> #include<cstdio> using namespace std; int maze[5][5]; //记录迷宫 struct node{ int x,y; }; //记录坐标 struct father{ int x,y; }; //父节点的坐标 father father[5][5]; //访问父节点 int vis[5][5]; //标记某点是否走过 int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; queue<node> q; stack<node> s; void bfs(); void output(); int outboard(int x,int y);//判断是否在边界里面 int main() { for(int i=0;i<5;++i) for(int j=0;j<5;j++) cin>>maze[i][j]; //输入迷宫 while(!q.empty())q.pop(); memset(vis,0,sizeof(vis)); bfs(); output(); return 0; } void bfs() { node a,next; a.x=0,a.y=0; q.push(a); while(!q.empty()) { a=q.front(); q.pop(); if(next.x==4&&next.y==4) { father[4][4].x=a.x; father[4][4].y=a.y; break; } //找到出口 for(int i=0;i<4;++i) { next.x=a.x+dx[i]; next.y=a.y+dy[i]; if(vis[next.x][next.y]||maze[next.x][next.y]||outboard(next.x,next.y)) continue; father[next.x][next.y].x=a.x; father[next.x][next.y].y=a.y; //储存其父节点的位置 vis[next.x][next.y]=1; //标记为该点走过 q.push(next); } //一轮试探 } } void output() { int x=4,y=4; node a; while(x||y) { a.x=x; a.y=y; s.push(a); x=father[x][y].x; y=father[x][y].y; } //子节点进栈其父结点进栈父节点的父节点进栈。。。 a.x=0,a.y=0; s.push(a); while(!s.empty()) { printf("(%d,%d)\n",s.top().x,s.top().y); s.pop(); } } int outboard(int x,int y) { if(x<0||x>=5||y<0||y>=5) return 1; return 0; }//判断是否出边界