题解 P6410 【[COCI2008-2009#3] CROSS】
这题看起来很麻烦，可是写起来好像比较简单（吗？）。
官方代码中变量命名不是英文，看不懂在写什么。。。
还是自己写了一下。
I. 题意
首先判定数独是否合法。
合法便需要反复使用交叉影线法，推导出格子的值。
II. 实现合法性判断
模拟。
首先判断行、列、宫是否有重复的。
(1) 用三个二维数组分别记录某个数字在某项目（每行、每列、每宫）有没有出现过。
(2) 遇到数字，把对应三个项目作注记。若在此前已有注记，说明这数独不合法。
然后判断是否每一个宫都能填入数字1-9。
如果发现某数字在某宫中只有一个位置能填入，那么马上填入。
如果只有这里没写对，会得到奇妙的97 pts。
流程是这样的...
那么对于每个数字进行检查，如果一个宫没有合法位置再填入这个数字（当然，这个宫本身没有这个数字的话），那就是不合法的。
如果只有一种可能的位置，那么就马上填入。
这部分时间复杂度是
III. 实现交叉影线法
如果像我那么懵懂的话，可能不知道要运用多少次才行，那么订一个大点的数，例如
每一次交叉影线法，我们对于每一个数字...
-
先开一个新的数组，用于剔除不合法位置。
-
剔除不合法位置，在新开的二维数组把这些位置标上状态不合法。
-
最后查看每一个宫，如果合法位置唯一，那么填入。
感觉讲得不太好，可以看看代码。
此部分时间复杂度是
IV. 代码
#include <iostream>
#include <cstdio>
using namespace std;
int line[11][11],column[11][11],gg[11][11];
char str[21];
int mat[11][11];
int get_gg(int i,int j)
{
int x=(i-1)/3+1;
int y=(j-1)/3+1;
return (x-1)*3+y;
}
int mat2[11][11];
int begingg[11],endgg[11];
int main()
{
int flag=0;
for (int i=1;i<=9;i++)
{
scanf("%s",str+1);
for (int j=1;j<=9;j++)
{
if (str[j]!='.')
{
mat[i][j]=str[j]-48;
if (line[i][mat[i][j]]) flag=1;
else line[i][mat[i][j]]=1;
if (column[j][mat[i][j]]) flag=2;
else column[j][mat[i][j]]=1;
if (gg[get_gg(i,j)][mat[i][j]]) flag=3;
else gg[get_gg(i,j)][mat[i][j]]=1;
}
}
}
if (flag)
{
printf("ERROR");
return 0;
}
begingg[1]=1;begingg[2]=4;begingg[3]=7;
endgg[1]=3;endgg[2]=6;endgg[3]=9;
for (int i=1;i<=9;i++) //check every number
{
for (int indggx=1;indggx<=3;indggx++) //check every 3*3 block
{
for (int indggy=1;indggy<=3;indggy++)
{
if (gg[(indggx-1)*3+indggy][i]==1) continue;
int tmpflag=0;
for (int indline=begingg[indggx];indline<=endgg[indggx];indline++) //we want each 3*3 block has this number, or keep a possible position for this number
{
for (int indcolumn=begingg[indggy];indcolumn<=endgg[indggy];indcolumn++)
{
if (line[indline][i]||column[indcolumn][i]||gg[get_gg(indline,indcolumn)][i]||mat[indline][indcolumn]) continue;
tmpflag++; //if this place is possible, it shows that this block is likely to be following the rules
}
}
if (!tmpflag) {flag=true;}
if (tmpflag==1)
{
for (int indline=begingg[indggx];indline<=endgg[indggx];indline++) //we want each 3*3 block has this number, or keep a possible position for this number
{
for (int indcolumn=begingg[indggy];indcolumn<=endgg[indggy];indcolumn++)
{
if (line[indline][i]||column[indcolumn][i]||gg[get_gg(indline,indcolumn)][i]||mat[indline][indcolumn]) continue;
line[indline][i]=1;
column[indcolumn][i]=1;
gg[get_gg(indline,indcolumn)][i]=1;
mat[indline][indcolumn]=i;
}
}
}
}
}
}
if (flag)
{
printf("ERROR");
return 0;
}
for (int tt=1;tt<=500;tt++) //number of using this method -- 500
{
for (int en=1;en<=9;en++) //for each number
{
for (int i=1;i<=9;i++) //clear data
{
for (int j=1;j<=9;j++) mat2[i][j]=0;
}
for (int inx=1;inx<=9;inx++) //cancel impossible unit
{
for (int iny=1;iny<=9;iny++)
{
if (mat[inx][iny]==en)
{
for (int i=1;i<=9;i++) //mark down impossible unit
{
mat2[inx][i]=1;
mat2[i][iny]=1;
}
for (int i=begingg[(inx-1)/3+1];i<=endgg[(inx-1)/3+1];i++)
{
for (int j=begingg[(iny-1)/3+1];j<=endgg[(iny-1)/3+1];j++)
{
mat2[i][j]=1;
}
}
}
if (mat[inx][iny])
{
mat2[inx][iny]=1;
}
}
}
for (int i=1;i<=3;i++) //we check through every 3*3 block to find out which place can be filled in
{
for (int j=1;j<=3;j++)
{
if (gg[(i-1)*3+j][en]) continue;
for (int indline=begingg[i];indline<=endgg[i];indline++)
{
for (int indcolumn=begingg[j];indcolumn<=endgg[j];indcolumn++)
{
if (mat2[indline][indcolumn]==0)
{
flag++;
}
}
}
if (flag==1)
{
for (int indline=begingg[i];indline<=endgg[i];indline++)
{
for (int indcolumn=begingg[j];indcolumn<=endgg[j];indcolumn++)
{
if (mat2[indline][indcolumn]==0)
{
mat[indline][indcolumn]=en;gg[get_gg(indline,indcolumn)][en]=1;
}
}
}
}
}
}
}
}
for (int i=1;i<=9;i++)
{
for (int j=1;j<=9;j++)
{
if (mat[i][j])
{
printf("%d",mat[i][j]);
}
else printf(".");
}
printf("\n");
}
}