DFS可解决。
#include <cstdio> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define rep(i, l, r) for(int i=l; i<=r; i++) #define down(i, l, r) for(int i=l; i>=r; i--) #define maxn 23 #define MAX 1<<30 using namespace std; int n, m, t, map[2][maxn][maxn], sx, sy, sz, tx, ty, tz, d[2][maxn][maxn]; char s[15]; void Search(int z, int x, int y, int c) { if (map[z][x][y] < 0) return; if (d[z][x][y] <= c) return; else d[z][x][y] = c; if (map[z][x][y] > 0) Search(1-z, x, y, c); else { Search(z, x, y+1, c+1); Search(z, x, y-1, c+1); Search(z, x+1, y, c+1); Search(z, x-1, y, c+1); } } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &t); rep(i, 1, n) { scanf("%s", s); rep(j, 1, m) if (s[j-1] == 'S') sx = i, sy = j, sz = 0, map[0][i][j] = 0; else if (s[j-1] == 'P') tx = i, ty = j, tz = 0, map[0][i][j] = 0; else if (s[j-1] == '*') map[0][i][j] = -1; else if (s[j-1] == '#') map[0][i][j] = 1; else map[0][i][j] = 0; } rep(i, 1, n) { scanf("%s", s); rep(j, 1, m) if (s[j-1] == 'S') sx = i, sy = j, sz = 1, map[1][i][j] = 0; else if (s[j-1] == 'P') tx = i, ty = j, tz = 1, map[1][i][j] = 0; else if (s[j-1] == '*') map[1][i][j] = -1; else if (s[j-1] == '#') map[1][i][j] = 1; else map[1][i][j] = 0; } rep(i, 0, n+1) map[0][i][0] = map[0][i][m+1] = map[1][i][0] = map[1][i][m+1] = -1; rep(i, 0, m+1) map[0][0][i] = map[0][n+1][i] = map[1][0][i] = map[1][n+1][i] = -1; rep(z, 0, 1) rep(x, 1, n) rep(y, 1, m) d[z][x][y] = MAX; Search(sz, sx, sy, 0); if (d[tz][tx][ty] <= t) printf("YES "); else printf("NO "); } return 0; }