自动搬运

查看原文

来自洛谷，原作者为

	Rain_chr think twice,code once

搬运于2025-08-24 22:20:31，当前版本为作者最后更新于2022-08-02 22:16:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在本人看来，这道题是一个大模拟

不升绿都对不起我的付出

题意简述

给定网格，完成以下任务：

• 判断给定的网格是否合法。

• 反复使用交叉影线发，直至所有格子都无法根据已有信息推断出当前格子的数值。

题目分析

我的做法是直接模拟，先填充，如果填充时发现有矛盾，就判定此网格非法。

1. 划掉格子

遍历每一个格子，如果这个格子中有数字且从未被遍历过，就进行筛法：

先将这个格子的所有可能性全部划掉，因为这个格子已经有数字了。

再将与其同行、同列、同宫的格子全部划掉。

特别注意：只是将关于这个格子中的数字的可能性划掉，而不是所有。

2.填充格子

遍历每一个格子，如果这一个格子还没填充且可能性只有一个，就将这只可能的数填入这个格子。

关于什么时候截止，我的做法是当所有格子都没有变动后，跳出循环。

3.判断合法

我分了三个情况：

1. 没填充的格子没有任何能填充的数字

2. 填充了的格子行列有重复

3. 填充了的九宫格有数不可能出现

虽然不全，但对这个题目够用了

重要提示：

• 请严格按照题面来，不要把这道题想象成数独。

• 按照数独的方法去做，只有七十分。

因为这道题里，他的方法有缺陷，不能把所有能填充的格子填充。

有一个测试点，这一列有八个数，就空缺了一个格子，且输入合法，我七十分的代码能处理剩下的格子，但AC代码和标准代码不行。测试点输出中这个格子也是空着的。

然后就是愉快的交代码了！

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int value;
	int checked;
	int maybe[10];
}a[10][10]; //这是地图
int b[10][10]; 
void init() //这个预处理是判断两个数在不在一个九宫格内的。这是以时间换省事，大家不要学。
{
	int ti=1;
	for(int i=1;i<=9;i+=3)
	{
		for(int j=1;j<=9;j+=3)
		{
			for(int k1=0;k1<3;k1++)
			{
				for(int k2=0;k2<3;k2++)
				{
					b[i+k1][j+k2]=ti;

				}
			}
			ti++;
		}
	}
}
bool check() //三条判断
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			if(a[i][j].value>0)
				continue;
			int k=0;
			for(int x=1;x<=9;x++)
				k+=a[i][j].maybe[x];
			if(k==9)
				return 1; 
		}
	}
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			if(a[i][j].value<1)
				continue;
			for(int k=1;k<=9;k++)
			{
				if(k==j||k==i)
					continue;
				if(a[i][j].value==a[i][k].value||a[i][j].value==a[k][j].value)
					return 1;
			}
		}
	}
	for(int k=1;k<=9;k++)
	{
		for(int i=1;i<=9;i+=3)
		{
			for(int j=1;j<=9;j+=3)
			{
				int num=0;
				for(int k1=0;k1<3;k1++)
					for(int k2=0;k2<3;k2++)
						num+=a[i+k1][j+k2].maybe[k];
				if(num==9)
				{
					bool f=0;
					for(int k1=0;k1<3;k1++)
						for(int k2=0;k2<3;k2++)
							if(a[i+k1][j+k2].value==k)
							{
								f=1;
								break;
							}
					if(!f)
						return 1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	init();
	string s;
	for(int i=1;i<=9;i++)
	{
		cin>>s;
		for(int j=0;j<s.size();j++)
			a[i][j+1].value=s[j]-'0',a[i][j].checked=0;
	}

	bool flag=1;
	while(flag)
	{
		flag=0;
		for(int i=1;i<=9;i++) //交叉影线
		{
			for(int j=1;j<=9;j++)
			{
				if(a[i][j].value>0&&!a[i][j].checked)
				{
					for(int k=1;k<=9;k++)
						a[i][j].maybe[k]=1;
					for(int k=1;k<=9;k++)
						a[i][k].maybe[a[i][j].value]=1;
					for(int k=1;k<=9;k++)
						a[k][j].maybe[a[i][j].value]=1; 
					for(int k1=1;k1<=9;k1++)
					{
						for(int k2=1;k2<=9;k2++)
						{
							if(b[k1][k2]==b[i][j])
								a[k1][k2].maybe[a[i][j].value]=1;
						}
					}
					flag=1;
					a[i][j].checked=1;
				}
			}
		}
		
		for(int k=1;k<=9;k++) //填格 
		{
			for(int i=1;i<=9;i+=3)
			{
				for(int j=1;j<=9;j+=3)
				{
					int num=0,x,y;
					for(int k1=0;k1<3;k1++)
					{
						for(int k2=0;k2<3;k2++)
						{
							if(a[i+k1][j+k2].maybe[k]==0)
							{
								num++;
								x=i+k1;
								y=j+k2;	
							} 
						}
					}
					if(num==1)
						a[x][y].value=k;
				}
			}
		} 
	}
	if(check())
	{
		cout<<"ERROR";
		return 0; 
	}
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			if(a[i][j].value>0)
				cout<<a[i][j].value;
			else
				cout<<'.';
		}
		cout<<endl;
	}
	return 0; //撒花！！！
}

整整一百七十行代码啊~花了我一下午

完结撒花！

等等！

还有能正确处理所有数独的七十分代码，就当做送给大家了！

数独代码

输入格式同本题

作者写了两个小时，点个赞再走吧~