题解：P10386 [蓝桥杯 2024 省 A] 五子棋对弈

· · 题解

P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解

思路

计划分为两步

  1. 直接暴力DFS出所有棋局的情况
  2. 检查有没有人赢，没有就计数++

    第一步

    先用两个变量 w,b 记录白/黑子的剩余数量，每层搜索分别判断有无白/黑子，有就在相应的位置落子并继续搜索。

    重点

    虽然搜索直接用 x,y 表示搜索的位置更方便，但我还是选择用只一个 p。 所以如何把这个 p 转换为 x,y 就是问题所在。上公式： x=(p-1) \div 5+1,y=(p-1) \bmod 5+1。如果你习惯 x,y 下标从 0 开始，这是公式： x=(p-1) \div 5,y=(p-1) \bmod 5。

    第二步

    for循环从 1 到 5，分别检查第 i 行/列是否全是白/黑子。对于对角线，我会给出通用的公式。左上-右下：y=x (1 \le x \le n)，右上-左下：y=n+1-x (1 \le x \le n)。这样检查两条对角线是否全是白/黑子。

    代码

    #include <bits/stdc++.h>
using namespace std;
int mapp[10][10];//棋盘
int w=13,b=12;//白黑子剩余数量
int cnt;//计数
void check(){
for (int i=1;i<=5;i++){//检查第i行/列
    if (mapp[i][1]&&mapp[i][2]&&mapp[i][3]&&mapp[i][4]&&mapp[i][5]) return ;//第i行全白
    if (!mapp[i][1]&&!mapp[i][2]&&!mapp[i][3]&&!mapp[i][4]&&!mapp[i][5]) return ;//第i行全黑
    if (mapp[1][i]&&mapp[2][i]&&mapp[3][i]&&mapp[4][i]&&mapp[5][i]) return ;//第i列全白
    if (!mapp[1][i]&&!mapp[2][i]&&!mapp[3][i]&&!mapp[4][i]&&!mapp[5][i]) return ;//第i列全黑
}
if (mapp[1][1]&&mapp[2][2]&&mapp[3][3]&&mapp[4][4]&&mapp[5][5]) return ;//左上-右下对角线全白
if (!mapp[1][1]&&!mapp[2][2]&&!mapp[3][3]&&!mapp[4][4]&&!mapp[5][5]) return ;//左上-右下对角线全黑
if (mapp[1][5]&&mapp[2][4]&&mapp[3][3]&&mapp[4][2]&&mapp[5][1]) return ;//右上-左下对角线全白
if (!mapp[1][5]&&!mapp[2][4]&&!mapp[3][3]&&!mapp[4][2]&&!mapp[5][1]) return ;//右上-左下对角线全黑
cnt++;//经过天衣无缝的检查后，这个棋局可以判定为和棋了
}
void dfs(int p){//搜索到第p位
if (p==26){//5*5填完了
    check();//检查
}
//白棋
if (w){//如果还有白棋
    w--;//白棋子数量--
    //好好看，好好学，搜索位数转坐标
    mapp[(p-1)/5+1][(p-1)%5+1]=1;//棋盘标记为白子
    dfs(p+1);//搜索下一个点位
    //回溯不用改棋盘，下次搜到这一位自然会改
    w++;//回溯
}
//黑棋
if (b){
    b--;
    mapp[(p-1)/5+1][(p-1)%5+1]=0;
    dfs(p+1);
    b++;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
dfs(1);//从第1位开始搜
cout<<cnt;//输出答案
return 0;
}
    小技巧

    该说还是得说，既然这题固定输出：

    #include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout<<3126376;
return 0;
}