思路
贪心,若问题有解,则可将坏人的空邻接点都堵上(有效拦住坏人,同时使影响范围尽可能小)。证明:假设存在一个方案可以使某些坏人的某些空邻接点不被堵上,则这些点一定无法到达 $(n, m)$。因此将坏人的空邻接点都堵上,好人仍然可以到达 $(n, m)$,再将可行解建立的墙拆除,坏人仍然无法到达 $(n, m)$,因此仍是可行解。补充:可行解中,坏人无法从有人的邻接点到达 $(n, m)$,因此不需要处理这些点。
时间复杂度 $O(nm)$。
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100;
int n, m;
char g[N][N];
bool vis[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] != '#' && !vis[a][b])
dfs(a, b);
}
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> g[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 'B')
for (int k = 0; k < 4; k++) {
int a = i + dx[k], b = j + dy[k];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
g[a][b] = '#';
}
memset(vis, 0, sizeof vis);
if (g[n - 1][m - 1] != '#')
dfs(n - 1, m - 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 'B' && vis[i][j] || g[i][j] == 'G' && !vis[i][j]) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}