贪心|Codeforces D. Solve The Maze (bfs & 贪心) (Round #648 Div.2) 比赛&训练|图论

传送门
题意：现有一个n * m 的迷宫，期间 '#'表示墙壁， '.'表示道路， 'G’表示好人， 'B’表示坏人。试问是否能通过将某些道路改建为墙壁，以使所有坏人不能从(n，m)出口逃出，而所有好人可以。

文章图片

思路：这题看似很复杂，其实是有规律的。

为了避免影响好人的逃生，应该在坏人的四周建立围墙
为了降低时间复杂度，应该以(n，m)为起点开始bfs()，标记所有能到达的点。最后遍历所以格点，若有好人未被标记就是"NO"，反之"YES"。

【贪心|Codeforces D. Solve The Maze (bfs & 贪心) (Round #648 Div.2)】代码实现：

#include #define endl '\n' #define null NULL #define ll long long #define pii pair #define lowbit(x) (x &(-x)) #define ls(x) x<<1 #define rs(x) (x<<1+1) #define me(ar) memset(ar, 0, sizeof ar) #define mem(ar,num) memset(ar, num, sizeof ar) #define rp(i, n) for(int i = 0, i < n; i ++) #define rep(i, a, n) for(int i = a; i <= n; i ++) #define pre(i, n, a) for(int i = n; i >= a; i --) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; using namespace std; const intinf = 0x7fffffff; const double PI = acos(-1.0); const double eps = 1e-6; const llmod = 1e9 + 7; const intN = 2e5 + 5; int t, n, m, ok; char mp[55][55]; bool vis[55][55]; struct node{ int x, y; }; void add(int x, int y) { for(int i = 0; i < 4; i ++){ int nx = x + way[i][0]; int ny = y + way[i][1]; if(nx > 0 && nx <= n && ny > 0 && ny <= m){ if(mp[nx][ny] == 'G') ok = 0; if(mp[nx][ny] == '.') mp[nx][ny] = '#'; } } } //常规bfs操作 void bfs(int n, int m) { queue q; vis[n][m] = 1; q.push((node){n, m}); while(!q.empty()){ node u = q.front(); q.pop(); for(int i = 0; i < 4; i ++){ int nx = u.x + way[i][0]; int ny = u.y + way[i][1]; if(nx > 0 && nx <= n && ny > 0 && ny <= m && !vis[nx][ny] && mp[nx][ny] != '#'){ vis[nx][ny] = 1; q.push((node){nx, ny}); } } } }signed main() { IOS; cin >> t; while(t --){ ok = 1; //切记要在主函数内初始化vis数组，否则若出口(n, m)为墙壁时不会进行bfs操作，上一组的vis数组数据就会影响这组的测试 me(vis); cin >> n >> m; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> mp[i][j]; //在坏人的周围修建墙壁 for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(mp[i][j] == 'B') add(i, j); if(mp[n][m] != '#') bfs(n, m); //遍历判断是否有无法逃生的好人 for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++) if(mp[i][j] == 'G' && !vis[i][j]) {ok = 0; break; } if(!ok) break; }if(ok) cout << "YES" << endl; else cout << "NO" << endl; }return 0; }