首页 > 代码库 > POJ - 3984 迷宫问题 bfs解法
POJ - 3984 迷宫问题 bfs解法
#include<stdio.h> #include<string.h> #include<algorithm> #include<stack> using namespace std; int a[5][5],b[5][5]; int di[4][2]={0,1,0,-1,1,0,-1,0}; void bfs(int x,int y) { int tx=x,ty=y,i; if(a[x][y]==0) { a[x][y]=1; for(i=0;i<4;i++) { tx+=di[i][0]; ty+=di[i][1]; if(a[tx][ty]==0&&tx>=0&&ty>=0&&tx<=4&&ty<=4) { b[tx][ty]=min(b[tx][ty],b[x][y]+1); } } for(i=0;i<4;i++) { tx+=di[i][0]; ty+=di[i][1]; if(a[tx][ty]==0&&tx>=0&&ty>=0&&tx<=4&&ty<=4) bfs(tx,ty); } } } int main() { stack<int>s1,s2; int i,j,ti,tj,k; for(i=0;i<5;i++) for(j=0;j<5;j++) scanf("%d",&a[i][j]); for(i=0;i<5;i++) for(j=0;j<5;j++) b[i][j]=999; b[0][0]=1; bfs(0,0); i=4;j=4; s1.push(4); s2.push(4); while(1) { if(j==0&&i==0) break; for(k=0;k<4;k++) { ti=i+di[k][0]; tj=j+di[k][1]; if(b[i][j]==b[ti][tj]+1 && ti>=0 && tj>=0 && ti<=4 && tj<=4) { s1.push(ti); s2.push(tj); i=ti;j=tj; // printf("%d %d\n",i,j); break; } } } while(s1.size()!=0) { i=s1.top();s1.pop(); j=s2.top();s2.pop(); printf("(%d, %d)\n",i,j); } return 0; }
POJ - 3984 迷宫问题 bfs解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。