P6410 【[COCI2008-2009#3] CROSS】题解
在本人看来，这道题是一个大模拟
不升绿都对不起我的付出
题意简述
给定网格，完成以下任务：
-
判断给定的网格是否合法。
-
反复使用交叉影线发，直至所有格子都无法根据已有信息推断出当前格子的数值。
题目分析
我的做法是直接模拟，先填充，如果填充时发现有矛盾，就判定此网格非法。
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; //撒花！！！
}整整一百七十行代码啊~花了我一下午
完结撒花！
等等！
还有能正确处理所有数独的七十分代码，就当做送给大家了！
数独代码
输入格式同本题
作者写了两个小时，点个赞再走吧~