首页 > 代码库 > (简单) POJ 3984 迷宫问题，BFS。
(简单) POJ 3984 迷宫问题，BFS。
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
水题，BFS然后记录路径就好。
代码如下：
#include<iostream>#include<cstring>#include<queue>#include<utility>using namespace std;typedef struct pair<int,int> pii;int vis[6][6];int fa[6][6];bool judge(int x,int y){ if(x<0||y<0||x>4||y>4) return 0; if(vis[x][y]) return 0; return 1;}void slove(){ queue < pii > que; pii temp,temp1; int t1,t2; que.push(make_pair(0,0)); vis[0][0]=1; while(!que.empty()) { temp=que.front(); que.pop(); t1=temp.first/5; t2=temp.first%5; fa[t1][t2]=temp.second; if(t1==4&&t2==4) return; --t1; if(judge(t1,t2)) { vis[t1][t2]=1; temp1=make_pair(t1*5+t2,temp.first); que.push(temp1); } t1+=2; if(judge(t1,t2)) { vis[t1][t2]=1; que.push(make_pair(t1*5+t2,temp.first)); } --t1; --t2; if(judge(t1,t2)) { vis[t1][t2]=1; que.push(make_pair(t1*5+t2,temp.first)); } t2+=2; if(judge(t1,t2)) { vis[t1][t2]=1; que.push(make_pair(t1*5+t2,temp.first)); } }}void showans(){ int cou=0; int ans[30]; int temp=24; while(temp) { ans[cou++]=temp; temp=fa[temp/5][temp%5]; } cout<<"(0, 0)"<<endl; for(int i=cou-1;i>=0;--i) cout<<‘(‘<<ans[i]/5<<", "<<ans[i]%5<<‘)‘<<endl;}int main(){ ios::sync_with_stdio(false); while(cin>>vis[0][0]) { for(int j=1;j<5;++j) cin>>vis[0][j]; for(int i=1;i<5;++i) for(int j=0;j<5;++j) cin>>vis[i][j]; slove(); showans(); } return 0;}
(简单) POJ 3984 迷宫问题，BFS。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。