codeforce1365D. Solve The Maze

この世界も悪くない
把迷宫里坏人全困住,好人能走出来


首先把坏人圈出来,然后统计与出口连通的好人的数量,据此判断。
如果有坏人和好人相邻,那么一定是no。因为好人最后能出去,而坏人与好人连通且不能阻隔,所以最后坏人也就出去了。
注意坏人与坏人相邻时,不能将这个相邻位置直接换成墙

#pragma GCC diagnostic error "-std=c++11"
#include bits/stdc++.h
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pairint,int
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;indexfinish;index++)
#define drep(index,finish,star) for(register int index=finish;index=star;index--)
using namespace std;

templateclass T void _deb(const char *name,T val){
    coutnamevalendl;
}
const int move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int n,m;
char maze[55][55];
inline bool isBlocked(int x,int y);
int dfs(int x,int y);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    short T;
    cinT;
    while(T--){
        cinnm;
        rep(i,0,n)
            cinmaze[i];

        int numOfG=0;
        rep(i,0,n){
            rep(j,0,m){
                switch(maze[i][j]){
                    case 'G':
                        numOfG++;
                        break;
                    case 'B':
                        rep(k,0,4){
                            int nextX=i+::move[k][0];
                            int nextY=j+::move[k][1];
                            if(!isBlocked(nextX,nextY)  maze[nextX][nextY]!='B'){
                                numOfG+=maze[nextX][nextY]=='G';
                                maze[nextX][nextY]='#';
                            }
                        }
                        break;
                }
            }
        }
        if(!numOfG){
            cout"yes"endl;
            continue;
        }

        if(maze[n-1][m-1]=='#')
            cout"no"endl;
        else
            cout(dfs(n-1,m-1)==numOfG? "yes":"no")endl;
    }

    re 0;
}
inline bool isBlocked(int x,int y){
    if(x0||x=n||y0||y=m||maze[x][y]=='#')
        re true;
    re false;
}
int dfs(int x,int y){
    int sum=maze[x][y]=='G'?1:0;
    maze[x][y]='#';

    rep(i,0,4){
        int nextX=x+::move[i][0];
        int nextY=y+::move[i][1];

        if(!isBlocked(nextX,nextY)){
            sum+=dfs(nextX,nextY);
        }
    }
    re sum;
}

最新回复(0)
/jishuMghB5P6PJ5VVhc6udFFGuIxc8TZefWn21UEZRw_3D_3D4795020
8 简首页