题解：P10419 [蓝桥杯 2023 国 A] 01 游戏

Clare613 · 2024-10-03 16:36:46 · 题解

题意

找一个符合条件的二维 01 数组。

分析

二维 01 数组是可以通过搜索得到的，因此我们搜索出所有情况的 01 数组，然后判断是否成立即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[15][15];
int c0[15],c1[15];
char b[15][15];
bool flag=0;
bool d1(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            bool fl=0;
            for(int k=1;k<=n;k++){
                if(a[i][k]!=a[j][k]){
                    fl=1;
                    break;
                }
            }
            if(fl==0){
                 return 0;
            }
        }
    }
    return 1;
}
bool d2(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            bool fl=0;
            for(int k=1;k<=n;k++){
                if(a[k][i]!=a[k][j]){
                    fl=1;
                    break;
                }
            }
            if(fl==0){
                 return 0;
            }
        }
    }
    return 1;
}
void dfs(int x,int y){
    if(c0[y]>n/2||c1[y]>n/2) return ;
    if(flag) return ;
    if(x>2){
        if(a[x][y]==a[x-1][y]&&a[x-1][y]==a[x-2][y]){
            return ;
        }
    }
    if(y>2){
        if(a[x][y]==a[x][y-1]&&a[x][y-1]==a[x][y-2]){
            return ;
        }
    }
    if(x==n&&y==n){
        for(int i=1;i<=n;i++){
            int sum0=0,sum1=0;
            for(int j=1;j<=n;j++){
                if(a[i][j]==0) sum0++;
                if(a[i][j]==1) sum1++;
            }
            if(sum0!=sum1||sum0!=n/2){
                return ;
            }
        }
        if(d1()==0||d2()==0) return ;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<a[i][j];
            }
            cout<<"\n";
        }
        flag=1;
        return ;
    }
    x++;
    if(x>n){
        x=1;
        y++;
    }
    if(b[x][y]=='_'){
        a[x][y]=0;
        c0[y]++;
        dfs(x,y);
        c0[y]--;
        c1[y]++;
        a[x][y]=1;
        dfs(x,y);
        c1[y]--;
    }
    else{
        if(b[x][y]=='0'){
            a[x][y]=0;
            c0[y]++;
            dfs(x,y);
            c0[y]--;
        }
        else{
            a[x][y]=1;
            c1[y]++;
            dfs(x,y);
            c1[y]--;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>b[i][j];
        }
    }
    if(b[1][1]=='_'){
        a[1][1]=0;
        c0[1]++;
        dfs(1,1);
        c0[1]--;
        c1[1]++;
        a[1][1]=1;
        dfs(1,1);
    }
    else{
        if(b[1][1]=='0'){
            c0[1]++;
            a[1][1]=0;
            dfs(1,1);
        }
        else{
            c1[1]++;
            a[1][1]=1;
            dfs(1,1);
        }
    }
    return 0;
}