0分,在本地运行时还出现RE
查看原帖
0分,在本地运行时还出现RE
672360
Ch35楼主2022/7/19 20:06

0分

#include<bits/stdc++.h>
using namespace std;
int n,m,q,fi_x,fi_y,cow_x,cow_y,box_x,box_y;
bool b[1501][1501];
char a[1501][1501];
string ans[2]={"NO","YES"};
bool dfs(int cow_x,int cow_y,int box_x,int box_y){
    if(box_x==fi_x&&box_y==fi_y){
        return 1; 
    }
    if(cow_x-1>0&&a[cow_x-1][cow_y]!='#'&&b[cow_x-1][cow_y]==0){
        if(cow_x-1==box_x&&cow_y==box_y&&box_x-1>0&&a[box_x-1][box_y]!='#'){
            b[cow_x-1][cow_y]=1;
            if(dfs(cow_x-1,cow_y,box_x-1,box_y))return 1;
            b[cow_x-1][cow_y]=0;
        } 
        else{
            if((cow_x-1==box_x&&cow_y==box_y)&&(!(box_x-1>0||a[box_x-1][box_y]!='#')));
            else{
                b[cow_x-1][cow_y]=1;
                if(dfs(cow_x-1,cow_y,box_x,box_y))return 1;
                b[cow_x-1][cow_y]=0;
            }
        }
    }
    if(cow_y-1>0&&a[cow_x][cow_y-1]!='#'&&b[cow_x][cow_y-1]==0){
        if(cow_x==box_x&&cow_y-1==box_y&&box_y-1>0&&a[box_x][box_y-1]!='#'){
            b[cow_x][cow_y-1]=1;
            if(dfs(cow_x,cow_y-1,box_x,box_y-1))return 1;
            b[cow_x][cow_y-1]=0;
        } 
        else{
            if((cow_x==box_x&&cow_y-1==box_y)&&(!(box_y-1>0||a[box_x][box_y-1]!='#')));
            else{
                b[cow_x][cow_y-1]=1;
                if(dfs(cow_x,cow_y-1,box_x,box_y))return 1;
                b[cow_x][cow_y-1]=0;
            }
        }
    }
    if(cow_y+1<=m&&a[cow_x][cow_y+1]!='#'&&b[cow_x][cow_y+1]==0){
        if(cow_x==box_x&&cow_y+1==box_y&&box_y+1<=m&&a[box_x][box_y+1]!='#'){
            b[cow_x][cow_y+1]=1;
            if(dfs(cow_x,cow_y+1,box_x,box_y+1))return 1;
            b[cow_x][cow_y+1]=0;
        } 
        else{
            if((cow_x==box_x&&cow_y+1==box_y)&&(!(box_y+1<=m||a[box_x][box_y+1]!='#')));
            else{
                b[cow_x][cow_y+1]=1;
                if(dfs(cow_x,cow_y+1,box_x,box_y))return 1;
                b[cow_x][cow_y+1]=0;
            }
        }
    }
    if(cow_x+1<=n&&a[cow_x+1][cow_y]!='#'&&b[cow_x+1][cow_y]==0){
        if(cow_x+1==box_x&&cow_y==box_y&&box_x+1<=n&&a[box_x+1][box_y]!='#'){
            b[cow_x+1][cow_y]=1;
            if(dfs(cow_x+1,cow_y,box_x+1,box_y))return 1;
            b[cow_x+1][cow_y]=0;
        } 
        else{
            if((cow_x+1==box_x&&cow_y==box_y)&&(!(box_x+1<=n||a[box_x+1][box_y]!='#')));
            else{
                b[cow_x+1][cow_y]=1;
                if(dfs(cow_x+1,cow_y,box_x,box_y))return 1;
                b[cow_x+1][cow_y]=0;
            }
        }
    }
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=m;j++){
	        cin>>a[i][j];
	        if(a[i][j]=='A')cow_x=i,cow_y=j;
	        if(a[i][j]=='B')box_x=i,box_y=j;
        }
    }
    while(q--){
        cin>>fi_x>>fi_y;
        if(a[fi_x][fi_y]=='#'){
            cout<<"NO";
            continue;
        }
        memset(b,0,n*m);
        b[cow_x][cow_y]=1;
        cout<<ans[dfs(cow_x,cow_y,box_x,box_y)]<<endl;
    }
	return 0;
}

2022/7/19 20:06
加载中...