比赛 二进制状态表示之搜索中的应用 评测结果 AAAAAAAA
题目名称 城堡 最终得分 100
用户昵称 宇战 运行时间 0.372 s
代码语言 C++ 内存使用 1.90 MiB
提交时间 2023-07-27 08:36:32
显示代码纯文本
    #include<bits/stdc++.h>
    using namespace std;
    int vis[100][100],a[100][100],fil[100][100],qq[100][100],ss;
    int n,m,s,ans,shu,maxx=0,top;
    int op[100][100][5];
    struct node{
        int x,y,z,p;
    }b[100000];
    bool cmp(node x,node y){
        if(x.p==y.p){
            if(x.y==y.y){
                    return x.x>y.x;
            }else{
                return x.y<y.y;
            }
        }else{
            return x.p>y.p;
        }
    }
    void init(){
        cin>>m>>n;
        memset(vis,1,sizeof(vis));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                    cin>>a[i][j];
                    vis[i][j]=0;
                    int t=a[i][j],o=0;
                    for(;t;t>>=1){
                        o++;
                        if(t&1){
                            if(o==1){
                                op[i][j][1]=1;
                            }
                            if(o==2){
                                op[i][j][2]=1;
                            }
                            if(o==3){
                                op[i][j][3]=1;
                            }
                            if(o==4){
                                op[i][j][4]=1;
                            }
                        }
                    }
            }
        }
    }
    void dfs(int x,int y){
        if(fil[x][y]==0){
            fil[x][y]=ss;
        }
        if(vis[x][y-1]==0&&op[x][y][1]==0){
            vis[x][y-1]=1;
            ss++;
            dfs(x,y-1);
        }
        if(vis[x-1][y]==0&&op[x][y][2]==0){
            vis[x-1][y]=1;
            ss++;
            dfs(x-1,y);
        }
        if(vis[x][y+1]==0&&op[x][y][3]==0){
            vis[x][y+1]=1;
            ss++;
            dfs(x,y+1);
        }
        if(vis[x+1][y]==0&&op[x][y][4]==0){
            vis[x+1][y]=1;
            ss++;
            dfs(x+1,y);
        }
    }
    void zh(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
           if(vis[i][j]==0){
               ss = 1;
               vis[i][j]=1;
               dfs(i,j);
           } 
        }
    }
    memset(vis,1,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vis[i][j]=0;
        }
    }
    }
    void mm(){
    shu=0,maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                if(fil[i][j]==1){
                    shu++;
                }
                maxx=max(maxx,fil[i][j]);
        }
    }
    memset(fil,0,sizeof(fil));
    }
    void wall(int x,int y){
        if(op[x][y][2]&&x!=1){
            op[x][y][2]=0;
            op[x-1][y][4]=0;
            zh();
            mm();
            ans=max(ans,maxx);
            b[++top].x=x;
            b[top].y=y;
            b[top].z=2;
            b[top].p=maxx;
            op[x-1][y][4]=1;
            op[x][y][2]=1;
            return;
        }
        if(op[x][y][3]&&y!=m){
            op[x][y][3]=0;
            op[x][y+1][1]=0;
            zh();
            mm();
            ans=max(ans,maxx);
            b[++top].x=x;
            b[top].y=y;
            b[top].p=maxx;
            b[top].z=3;
            op[x][y][3]=1;
            op[x][y+1][1]=1;
            return;
        }
    }
    int main(){
        freopen("castle.in","r",stdin);
        freopen("castle.out","w",stdout);
    init();
    zh(); 
    mm(); 
    cout<<shu<<endl<<maxx<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                wall(i,j);
        }
    } 
    cout<<ans<<endl;
    sort(b+1,b+1+top,cmp);
    int pp=1;
    cout<<b[pp].x<<' '<<b[pp].y<<' ';
    if(b[1].z==2){
        cout<<"N";
    }else if(b[1].z==3){
        cout<<"E";
    }
    return 0;
    }