首页 > 代码库 > hdu1240/poj2225 BFS广搜的再理解
hdu1240/poj2225 BFS广搜的再理解
原题地址
HDUOJ
POJ
题目介绍
题意
这同样是一道搜索题,所不同的是要搜索的图是三维的而不是二维的。但这并没什么大的改变,只是增加了两个搜索的方向而已。
陷阱
要注意的地方是,所给出的起点终点的坐标是按照 列,行,层的顺序。
关于BFS
与DFS不同,BFS能保证所搜到的路径一定是最短路径,所以我们不需要维护一个多维(此处为3维)数组来记录访问到每一点的最小步数,只需要维护一个多维数组来标记是否走过就可以了。DFS中是要不停回溯来找最短路径的,但是BFS是不需要的。这是BFS本身的性质所决定的,BFS能保证第一次搜索到某一点时所走的路径就是到该点的最短路径。以后如果还能再走到该点,那么所走的路径一定是大于等于第一次搜索到的路径的。所以,BFS是不需要回溯的。(自己之前也有误解。。囧)
代码
#include<iostream> #include<queue> using namespace std; #include<cstdio> #include<cstring> #define INF 0x3f3f3f3f struct node { int x,y,z; int level; node(int i,int j,int k,int l):x(i),y(j),z(k),level(l){}; void set(int i,int j,int k,int l) { x=i; y=j; z=k; level=l; } }; int d[6][3]={0,1,0,0,-1,0,1,0,0,-1,0,0,0,0,1,0,0,-1}; char m[10][10][10]; bool used[10][10][10]; int s[3],e[3]; int n,step; queue<node> q; void bfs(int x,int y,int z) { int i,j,k,l; node pos(x,y,z,0); q.push(pos); used[x][y][z]=1; while(!q.empty()) { pos = q.front(); i = pos.x; j = pos.y; k = pos.z; l = pos.level; q.pop(); if(i==e[2]&&j==e[1]&&k==e[0]) { if(l<step) step=l; continue; } for(int t=0;t<6;t++) { x=i+d[t][0]; y=j+d[t][1]; z=k+d[t][2]; if(x<0||x>=n||y<0||y>=n||z<0||z>=n||m[x][y][z]!='O'||used[x][y][z]) continue; pos.set(x,y,z,l+1); used[x][y][z]=1; q.push(pos); } } } int main() { char str[6]; while(cin>>str>>n) { memset(used,0,sizeof used); step = INF; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) cin>>m[i][j][k]; cin>>s[0]>>s[1]>>s[2]>>e[0]>>e[1]>>e[2]; cin>>str; bfs(s[2],s[1],s[0]); if(step!=INF) cout<<n<<" "<<step<<endl; else cout<<"NO ROUTE"<<endl; } }
used数组表示是否走过,1为走过,0为没有走过。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。