自动搬运

查看原文

来自洛谷，原作者为

	sanhaoxuezha 呵呵，看来我真的不适合这个理性的世界呢 || 呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵 || 这个废物很呵呵，什么也没有留下 || 我永远讨厌小情侣 || 壶关条件U580316

搬运于2025-08-24 23:13:50，当前版本为作者最后更新于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;
}