Codeforces 1365D Solve The Maze

題目大意:

在一個 \(n * m\) 的矩陣中,有空地、壞人、好人和牆。你可以將空地變成牆來堵住壞人。\((n, m)\)為出口,是否存在一個方案使得矩陣中所有好人能夠走到出口,而所有壞人不能通過出口,相應的輸出\(Yes\)\(No\)

思路:

1.預處理:如果壞人和好人相鄰,那麼壞人一定可以走到隔壁好人,再通過好人的路徑走到終點,所以不符合, 輸出\(No\);

​ 如果當前方格為壞人,我們只有將他四周都堵住,他才能不會走到出口, 即將周圍空地變成牆。

2.試想一下,如何挨個判斷好人是否能走到出口,是不是太麻煩了,那麼反過來想,判斷出口\((n, m)\)能走到哪些好人方格則只用做一次\(bfs\)或者\(dfs\),如果能走則標記一下。

代碼:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
 
int n, m;
char a[N][N];
bool st[N][N];
int flag = 1, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
 
void dfs(int sx, int sy){
    for(int i = 0; i < 4; i++){
        int x = sx + dx[i], y = sy + dy[i];
        if(x >= 1 && x <= n && y >= 1 && y <= m){
            if(a[x][y] == 'G') flag = 0;
            if(a[x][y] == '.') a[x][y] = '#';
        }
       
    }
}
 
void bfs(int sx, int sy){
     queue<PII> q;
     q.push({sx, sy});
     while(q.size()){
         PII t = q.front();
         q.pop();
         for(int i = 0; i < 4; i++){
             int x = t.first + dx[i], y = t.second + dy[i];
             if(a[x][y] == '#' || st[x][y]) continue;
             if(x >= 1 && x <= n && y >= 1 && y <= m){
                st[x][y] = true;
                q.push({x, y});
             }
         }
 
     }   
}
 
int main(){
    int T;
    cin >> T;
    while(T--){
        flag = 1;
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                cin >> a[i][j];
 
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                if(a[i][j] == 'B')
                    dfs(i, j);
            }
        memset(st, 0, sizeof st);
        if(a[n][m] != '#') bfs(n, m);
 
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                if(a[i][j] == 'G'){
                    if(st[i][j] == false) flag = 0;
                }
            }
 
        if(flag) cout << "Yes" << endl;
        else cout << "No" << endl;
 
    }
    return 0;
}