题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2102
思路 题目有两个坑点
0.Output 说 能在T时刻 找到公主 就输出 YES 但实际上 只要在T时刻或者T时刻之前找到就可以了 1.如果传输机另一边 是 墙 那么就会被撞死 那如果另一边也是传输机 那么也是就会传来传去 也是行不通的
解决方法 如果 传输机另一边是墙 那么就把这个传输机设置为墙 如果传输机另一边也是传输机 那就把 这两个传输机都设置为墙
因为传输的时候是不需要花费时间的 所以假如我们当前的状态是在传输机上 我们只需要更改一下 楼层就可以了
然后就是BFS 了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 3e1 + 5; const int MOD = 1e9 + 7; int n, m, t; int Move[4][2] { -1, 0, 1, 0, 0,-1, 0, 1, }; string G[2][15]; int v[2][15][15]; int ans; int scur, sx, sy, ecur, ex, ey; struct node { int x, y, cur; int step; }; bool ok(int cur, int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || G[cur][x][y] == '*') return false; return true; } void bfs() { CLR(v, 0); node tmp; tmp.cur = scur; tmp.x = sx; tmp.y = sy; tmp.step = 0; v[tmp.cur][tmp.x][tmp.y] = 1; queue <node> q; q.push(tmp); while (!q.empty()) { node u = q.front(), V; q.pop(); if (u.x == ex && u.y == ey && u.cur == ecur) { if (u.step <= t) ans = 1; return; } if (u.step > t) return; for (int i = 0; i < 4; i++) { V.cur = u.cur; V.x = u.x + Move[i][0]; V.y = u.y + Move[i][1]; V.step = u.step + 1; if (ok(V.cur, V.x, V.y)) { if (G[V.cur][V.x][V.y] == '#') V.cur = !V.cur; if (v[V.cur][V.x][V.y] == 0) q.push(V); v[V.cur][V.x][V.y] = 1; } } } } int main() { int T; cin >> T; while (T--) { scanf("%d%d%d", &n, &m, &t); for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) cin >> G[i][j]; } for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < m; k++) { if (G[i][j][k] == '#') { if (G[!i][j][k] == '*') G[i][j][k] = '*'; else if (G[!i][j][k] == '#') { G[i][j][k] = G[!i][j][k] = '*'; } } else if (G[i][j][k] == 'S') { G[i][j][k] = '.'; scur = i; sx = j; sy = k; } else if (G[i][j][k] == 'P') { G[i][j][k] = '.'; ecur = i; ex = j; ey = k; } } } } ans = 0; bfs(); if (ans) printf("YES\n"); else printf("NO\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433114.html
相关资源：JAVA上百实例源码以及开源项目