首页 > 代码库 > HDU 2102 A计划 bfs
HDU 2102 A计划 bfs
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2102
题目大意：
这个就是简单的BFS， 需要注意的地方就是你进入传送阵后被传送到的地方是什么， 要是还是传送阵的话人就会被传送回来，此点要注意一下。
其他的基本没什么坑的地方，代码可以参考一下， 弱有疑问欢迎留言，随时解决。
#include <iostream>#include <vector>#include <stack>#include <cstdlib>#include <cmath>#include <cstdio>#include <cstring>#include <string>#include <queue>#include <algorithm>using namespace std;#define maxn 15#define INF 0xfffffff#define min(a,b) (a<b?a:b)#define max(a,b) (a>b?a:b)struct Point{ int x, y, z; int step;} Ps, Pe;char maps[2][maxn][maxn];bool vis[2][maxn][maxn];int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };int m, n, step;bool OK(Point P){ return P.x >= 0 && P.x < m && P.y >= 0 && P.y < n && maps[P.z][P.x][P.y] != ‘*‘ && !vis[P.z][P.x][P.y];}bool BFS(){ Point P, Pn; queue<Point> Q; Q.push(Ps); while( !Q.empty() ) { P = Q.front(); Q.pop(); if(P.step > step) return false; if(P.x == Pe.x && P.y == Pe.y && P.z == Pe.z) return true; for(int i=0; i<4; i++) { Pn.z = P.z; Pn.x = P.x + dir[i][0]; Pn.y = P.y + dir[i][1]; Pn.step = P.step + 1; if( OK(Pn) ) { vis[Pn.z][Pn.x][Pn.y] = true; if(maps[Pn.z][Pn.x][Pn.y] == ‘#‘ && maps[Pn.z^1][Pn.x][Pn.y] == ‘.‘ && !vis[Pn.z^1][Pn.x][Pn.y] ) { Pn.z = Pn.z^1; vis[Pn.z][Pn.x][Pn.y] = true; Q.push(Pn); } else if(maps[Pn.z][Pn.x][Pn.y] == ‘.‘) { Q.push(Pn); } } } } return false;}int main(){ int T; cin >> T; while(T--) { cin >> m >> n >> step; memset(vis,0,sizeof(vis)); for(int k=0; k<2; k++) { for(int i=0; i<m; i++) { cin >> maps[k][i]; for(int j=0; j<n; j++) { if(maps[k][i][j] == ‘S‘) Ps.x = i, Ps.y = j, Ps.z = k, Ps.step = 0, maps[k][i][j] = ‘.‘; if(maps[k][i][j] == ‘P‘) Pe.x = i, Pe.y = j, Pe.z = k, maps[k][i][j] = ‘.‘; } } } if( BFS() ) cout << "YES" <<endl; else cout << "NO" << endl; } return 0;}
HDU 2102 A计划 bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。