题解：P12224 [蓝桥杯 2023 国 Java B] 数和游戏

sanhaoxuezha · 2025-07-24 23:32:05 · 题解

本题为一道简单的搜索题，思维难度并不大，但码量较大。

可以用结构体来表示格子和条目

初始化就是将每个条目的数值和每个格子的所属条目记录。

搜索就是把每个格子中可填入的数搜一遍。

接着就没什么要说的了，就是初始化和搜索，主要讲解在代码里。

#include<bits/stdc++.h>

using namespace std;

//记录格子
struct Block
{
    int color;  //颜色
    int a,b;    //如果颜色为灰，记录条目
    int num;    //如果颜色为白，记录填入数字
    vector<int> item;   //如果颜色为白，记录所有所属的条目，其实这里可以用一个pair容器来记录，但为图方便，用vector记录
};

//记录条目
struct Line
{
    int lastx,lasty;    //条目中最后一个格子的坐标
    int remain; //条目中还未被填入的格子数量
    bool vis[10];   //记录每个数字是否被用过
};

const int N=20;

Block block[N][N];
Line line[N*N]; //其实这里开50就够了

int n,m;
bool flag=0;        //记录是否找到答案
int cnt=0;      //line数组大小，其实line数组完全可以用vector代替，但这样会比较麻烦

//输出
void output()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(block[i][j].color==2) cout<<'_';
            else cout<<block[i][j].num;
            cout<<' ';
        }
        cout<<'\n';
    }
}

//初始化
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(block[i][j].color==2)    //如果本格为灰色格子
            {
                if(block[i][j].b!=-1)   //竖条目
                {
                    line[cnt].remain=block[i][j].b;
                    line[cnt].lastx=i;
                    for(int k=j+1;k<=m;k++)
                    {
                        if(block[i][k].color==2) break;
                        line[cnt].lasty=k;
                        block[i][k].item.push_back(cnt);
                    }
                    cnt++;
                }
                if(block[i][j].a!=-1)   //横条目
                {
                    line[cnt].remain=block[i][j].a;
                    line[cnt].lasty=j;
                    for(int k=i+1;k<=n;k++)
                    {
                        if(block[k][j].color==2) break;
                        line[cnt].lastx=k;
                        block[k][j].item.push_back(cnt);
                    }
                    cnt++;
                }
            }
}

//搜索
void dfs(int k)
{
    if(k==n*m)  //终止条件
    {
        flag=1;
        output();
        return ;
    }
    int x=k/n+1,y=k%n+1;    //坐标
    if(block[x][y].color==2)    //如果本格颜色为灰，跳过
    {
        dfs(k+1);
        return ;
    }
    for(int i=1;i<=9;i++)   //枚举数字
    {
        bool flag2=1;
        for(int it:block[x][y].item)
            if(line[it].vis[i] || line[it].remain<i || (x==line[it].lastx && y==line[it].lasty && line[it].remain!=i))  //是否可以填
            {
                flag2=0;break;
            }
        if(!flag2) continue;    //若不可以，跳过
        block[x][y].num=i;  //填入
        for(int it:block[x][y].item)    //打标记
        {
            line[it].vis[i]=1;
            line[it].remain-=i;
        }
        dfs(k+1);
        if(flag) return ;
        block[x][y].num=0;
        for(int it:block[x][y].item)    //去标记
        {
            line[it].vis[i]=0;
            line[it].remain+=i;
        }
    }
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>block[i][j].color;
            if(block[i][j].color==2) cin>>block[i][j].a>>block[i][j].b;
        }
    init();
    dfs(0);

    return 0;
}