1 条题解
-
0
思路:先堵死坏人周围空地,再检查终点是否可通行;从终点 BFS 标记可达区域,最后验证所有坏人不可达、所有好人可达。
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; struct node { int x, y; }; void solve() { char a[60][60]; node good[3000]; // 好人(G)的坐标数组 node bad[3000]; // 坏人(B)的坐标数组 int good_cnt = 0; // 好人数量 int bad_cnt = 0; // 坏人数量 bool vis[60][60] = {false}; // BFS访问标记 int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++){ cin >> a[i][j]; if(a[i][j] == 'G'){ good[good_cnt] = {i, j}; // 结构体赋值 good_cnt++; } else if(a[i][j] == 'B'){ bad[bad_cnt] = {i, j}; bad_cnt++; } } } // 处理坏人周围的空地(堵墙) for(int k = 0; k < bad_cnt; k++){ int x = bad[k].x; int y = bad[k].y; // 检查四个方向,空地则堵墙 if (x - 1 >= 1 && a[x - 1][y] == '.') a[x - 1][y] = '#'; if (x + 1 <= n && a[x + 1][y] == '.') a[x + 1][y] = '#'; if (y - 1 >= 1 && a[x][y - 1] == '.') a[x][y - 1] = '#'; if (y + 1 <= m && a[x][y + 1] == '.') a[x][y + 1] = '#'; } // 特殊情况:终点被堵死 if(a[n][m] == '#'){ // 若有好人则无法到达,否则可行 cout << (good_cnt ? "No" : "Yes") << endl; return; } // BFS:从终点(n,m)出发标记可达区域 queue<node> q; q.push({n, m}); vis[n][m] = true; while (!q.empty()) { node cur = q.front(); q.pop(); int x = cur.x; int y = cur.y; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (a[nx][ny] == '#' || vis[nx][ny]) continue; vis[nx][ny] = true; q.push({nx, ny}); } } // 检查所有坏人是否不可达终点 for (int k = 0; k < bad_cnt; k++) { int x = bad[k].x; int y = bad[k].y; if (vis[x][y]) { cout << "No" << endl; return; } } // 检查所有好人是否都可达终点 for (int k = 0; k < good_cnt; k++) { int x = good[k].x; int y = good[k].y; if (!vis[x][y]) { cout << "No" << endl; return; } } // 所有条件满足 cout << "Yes" << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) solve(); return 0; }
- 1
信息
- ID
- 1143
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 13
- 已通过
- 6
- 上传者