题解：B4254 [科大国创杯小学组 2024] 博弈

· · 题解

由于本蒟蒻实在是太弱了，所以没有什么特别好的方法，直接暴力吧。这道题模拟即可，代码谈不上简洁但绝对易懂。主要思路是黑与白轮流下，判断某一步是否合法，如果合法就落子，不合法就标记一下，然后另一方下。循环下去后如果两方都无法落子，就判断胜负，将结果累加下去。

判断代码：


bool hf(int x,int y,int p){ //hf是合法的缩写
    bool pd=false;
    for(int i=0;i<8;i++){
        int x1=x+s[i];
        int y1=y+q[i];
        int cnt=0;
        while(x1>0&&y1>0&&x1<=n&&y1<=n&&a[x1][y1]==1-p){
            cnt++,x1+=s[i],y1+=q[i]; 
        } //没用continue因为不需要
        if(x1>0&&y1>0&&x1<=n&&y1<=n&&a[x1][y1]==p&&cnt>0){
            x1-=s[i],y1-=q[i];
            while(a[x1][y1]==1-p){
                a[x1][y1]=p;
                x1-=s[i],y1-=q[i];
            }
            pd=true;
        }
    }
    if(pd) a[x][y]=p;
    return pd;
}

这个判断代码有些麻烦，总体思路是延八个方向搜索，如果碰到边界或没落子的地方直接过,如果碰到非起点的同色子就将 pd 设为 true 。注意如果这一步成功不要直接break，继续看一看有没有新可以转换的棋子

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int s[8]={-1,-1,-1,0,0,1,1,1},q[8]={-1,0,1,-1,1,-1,0,1};
int x,y,z;
int n,a[6][6];
bool hf(int x,int y,int p)//hf 是合法的缩写
{
    bool pd=false;
    for(int i=0;i<8;i++){
        int x1=x+s[i];
        int y1=y+q[i];
        int cnt=0;
        while(x1>0&&y1>0&&x1<=n&&y1<=n&&a[x1][y1]==1-p){
            cnt++,x1+=s[i],y1+=q[i]; 
        }//没用 continue 因为不需要
        if(x1>0&&y1>0&&x1<=n&&y1<=n&&a[x1][y1]==p&&cnt>0){
            x1-=s[i],y1-=q[i];
            while(a[x1][y1]==1-p){
                a[x1][y1]=p;
                x1-=s[i],y1-=q[i];
            }
            pd=true;
        }
    }
    if(pd) a[x][y]=p;
    return pd;
}
void hei(bool pd);//bool 函数是判断上一次有没有成功落子
void bai(bool pd){
    bool p=false;
    int cmp[6][6];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cmp[i][j]=a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==-1&&hf(i,j,0)){
                p=true;
                hei(true);
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        a[i][j]=cmp[i][j];
                    }
                }       
            }
        }
    }
    if(!p){
        if(pd) hei(false);
        else{
            int h=0,b=0;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(a[i][j]==0) b++;
                    if(a[i][j]==1) h++;
                }
            }
            if(h>b) x++;
            else if(b>h) y++;
            else z++;
        }
    }
}
void hei(bool pd){
    bool p=false;
    int cmp[6][6];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cmp[i][j]=a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==-1&&hf(i,j,1)){
                p=true;
                bai(true);
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        a[i][j]=cmp[i][j];
                    }
                }       
            }
        }
    }
    if(!p){
        if(pd) bai(false);
        else{
            int h=0,b=0;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(a[i][j]==0) b++;
                    if(a[i][j]==1) h++;
                }
            }
            if(h>b) x++;
            else if(b>h) y++;
            else z++;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    bai(true);
    printf("%d %d %d",x,y,z);
    return 0; 
}

各位大佬不喜勿喷，有问题评论区留言