题解：P12139 [蓝桥杯 2025 省 A] 黑白棋

· · 题解

题意：

棋盘已经给定，按照要求填入棋子完善棋盘。

满足：

思路：

手玩也许能做。但是这里给出暴搜的做法。

首先建一个矩阵，让所有的黑子位置为 1，所有白字的位置为 0，所有没填棋子的位置为 -1。

我们 dfs 的时候用一个 pos 变量来记录当前枚举的位置，那么行就可以表示为 row=pos/6，列就可以表示为 col=pos \bmod 6。

考虑搜索过程，如果棋盘上这个位置已经有棋子了，那么直接跳过枚举下一个位置即可。如果这个位置没有棋子，那就从黑白棋子两个中枚举一个，同时要注意剪枝，枚举出来一个棋子可以接着就去判断是否个数已经大于 3，或者有 3 个以上的棋子相邻了。然后枚举的过程中可以额外加一个判断就是如果行满了或者列满了，就去检查以下这一行或者这一列有没有出现过，进行进一步剪枝。

然后考虑当 pos=36 时我们就搜索到了最后一个位置，那么这个时候就可以去判断整个棋盘是否符合题意了。为什么还要判断？因为如果棋盘上某位置有子我们直接进入下一层搜索了，而没有进行判断。只有枚举的时候我们进行了判断，所以还要再加一个最后答案的判断，这样这个题就做完啦。

代码：

#include<bits/stdc++.h>
using namespace std;
int grid[6][6] = {
    { 1, 0, 1, 0,-1,-1},
    {-1,-1,-1, 0,-1,-1},
    {-1,-1,-1, 1, 0, 0},
    {-1,-1,-1,-1,-1,-1},
    {-1,-1, 1,-1,-1, 1},
    {-1, 0,-1,-1, 1,-1}
};
//通过题目给出的图片能推出来 (1,3) 和 (3,4) 一定是黑子所以直接填进去
int black_row[6]={0},black_col[6]={0}; //维护行和列上的黑子个数
int white_row[6]={0},white_col[6]={0}; //维护行和列上的白子个数
unordered_set<string> vis_row,vis_col; //记录行和列出现的情况
string ans; //保存答案
int check() //检查最后的棋局
{
    unordered_set<string> r,c;
    for(int i=0;i<6;i++)
    {
        string rr="";
        for(int j=0;j<6;j++) rr+=to_string(grid[i][j]);
        if(r.count(rr)) return 0;
        r.insert(rr);
    }
    for(int i=0;i<6;i++)
    {
        string cc="";
        for(int j=0;j<6;j++) cc+=to_string(grid[j][i]);
        if(c.count(cc)) return 0;
        c.insert(cc);
    }
    return 1;
}
int solve(int pos)
{
    if(pos==36)
    {
        if(check())
        {
            ans="";
            for(int i=0;i<6;i++)
                for(int j=0;j<6;j++) ans+=to_string(grid[i][j]);
            return 1;
        }
        return 0;
    }
    int row=pos/6;int col=pos%6;
    if(grid[row][col]!=-1) return solve(pos+1);//这里直接进下一层
    for(int val=0;val<=1;val++)
    {
        if(!val) { if(white_row[row]>=3||white_col[col]>=3) continue; }
        else { if(black_row[row]>=3||black_col[col]>=3) continue; }
        //这里判断是否总个数已经超了
        if(col>=2&&grid[row][col-2]==val&&grid[row][col-1]==val) continue;
        if(row>=2&&grid[row-2][col]==val&&grid[row-1][col]==val) continue;
        //这里判断是否有连着的三个

        grid[row][col]=val;
        if(val) { black_row[row]++;black_col[col]++; } 
        else { white_row[row]++;white_col[col]++; }

        int flag=1;
        int full_row=(col==5);int full_col=(row==5);
        //这里比较有意思，行满了实际上是列到头了，所以是(col==5)。反之同理。
        string rowstr="",colstr="";
        if(full_row)
        {
            for(int i=0;i<6;i++) rowstr+=to_string(grid[row][i]);
            if(vis_row.count(rowstr)) flag=0;
            else vis_row.insert(rowstr);
        }
        if(full_col)
        {
            for(int i=0;i<6;i++) colstr+=to_string(grid[i][col]);
            if(vis_col.count(colstr)) flag=0;
            else vis_col.insert(colstr);
        }
        if(flag&&solve(pos+1)) return 1;
        //这里是在判断是否已经有出现过的行和列了，进一步剪枝
        if(full_row) vis_row.erase(rowstr);
        if(full_col) vis_col.erase(colstr);
        grid[row][col]=-1;
        if(val) { black_row[row]--;black_col[col]--; }
        else { white_row[row]--;white_col[col]--; }
        //这里是搜索的回溯
    }
    return 0;
}
int main()
{
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
        {
            if(grid[i][j]==1) { black_row[i]++;black_col[j]++; }
            else if(grid[i][j]==0) { white_row[i]++;white_col[j]++; } 
        }
    }
    if(solve(0)) cout<<ans<<endl;
    return 0; 
}

细节还是挺多的，可以结合注释和代码再理解理解。