Codeforces 1365D Solve The Maze

Codeforces 1365D Solve The Maze

题目大意：

在一个 \(n * m\) 的矩阵中，有空地、坏人、好人和墙。你可以将空地变成墙来堵住坏人。\((n, m)\)为出口，是否存在一个方案使得矩阵中所有好人能够走到出口，而所有坏人不能通过出口，相应的输出\(Yes\) 和 \(No\)。

思路：

1.预处理：如果坏人和好人相邻，那么坏人一定可以走到隔壁好人，再通过好人的路径走到终点，所以不符合， 输出\(No\);

如果当前方格为坏人，我们只有将他四周都堵住，他才能不会走到出口, 即将周围空地变成墙。

2.试想一下，如何挨个判断好人是否能走到出口，是不是太麻烦了，那么反过来想，判断出口\((n, m)\)能走到哪些好人方格则只用做一次\(bfs\)或者\(dfs\),如果能走则标记一下。

代码：

#includeusing namespace std;
typedef pairPII;
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){
     queueq;
     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;
}www.bdsoba.com    www.awaedu.com
www.zuowenge.cn