题解 P4573 【[CQOI2013]新数独】
Juan_feng
2018-05-25 19:23:22
这道题居然没有人发题解，~~那本蒟蒻就来水一篇吧。~~
## 先来说说思路
**先不要把这道题想的太难了，你可以把这道题看成一个标准的数独加上几个判断。那么这道题就是标准的dfs，把9*9的方阵从头到尾搜一遍，判断每一个格子能否放1-9之间的数就行了。**
### 整理一下判断条件：
1.这一行是否有重复的数
2.这一列是否有重复的数
3.这一个小九宫格中是否有重复的数
4.是否符合大于小于的条件
**现在我分别用 _ h[i][j] ,l[i][j] ,g[i][j] _ 来表示第i行，第i列，第i个小九宫格中数字j是否重复。还有一个大于小于号的问题后面再说，让我们先来看一下读入。**
输入格式：
一共15行，包含一个新数独的实例。第奇数行包含左右方向的符号（<和>），第偶数行包含上下方向的符号（^和v）
**说是奇数行包含左右方向的符号，偶数行包含上下方向的符号，其实如果你仔细的看一下题目或者样例输入的话，应该不难发现输入格式的描述略有问题，有的行与输入描述是相反的。。。（如果已经改过来了就当我没说）**
**其实可以这样看：输入是有15行的，你可以把这15行分成3组，每组5行，这样描述就对了，每一组的奇数行和偶数行按描述进行读入即可**。
**读入符号之后，先看这个符号属于哪一个小九宫格（因为不同小九宫格的符号是不相关的），然后就要用到下面这个数组了:**
>#### f[i][x][y]
**它表示第i个小九宫格中第x个数和第y个数是否有大小关系。
读入的时候如果是">"或者"v"就在相应的位置保存1，如果是"<"或"^"就保存2。**
**那么这样一来符号的问题就不是问题了，在选数的时候多加一个循环判断一下这个数周围的大小关系是否合法不就行了？**
## 那么代码如下：
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;i++)
using namespace std;
int a[10][10],h[10][10],l[10][10],g[10][10],m,n,c,f[10][10][10];
void dfs(int x,int y)
{
if(x==9&&y==10) //终止条件
{
FOR(i,1,9) //输出填好的数独
{
FOR(j,1,9)
printf("%d ",a[i][j]);
cout<<endl;
}
exit(0); //因为保证唯一解，所以搜到一个就退出
}
if(y==10) //搜索换行条件
{
x=x+1;y=1;
}
FOR(i,1,9) //枚举这一个格子中的数字（1~9）
{
bool bl=0;
int g1=((x-1)/3)*3,g2=(y-1)/3,g3=g1+g2; //判断这个点在哪个小九宫格中（0~8）
if(g[g3][i]==1||h[x][i]==1||l[y][i]==1) //判断行，列和小九宫格中是否用过该数字
continue;
FOR(j,1,9) // 小九宫格中大于小于号的情况
{
int ii=(x-1)%3*3+(y-1)%3+1; //将坐标xy转为在九宫格内的序号（1~9）
if(f[g3][ii][j]==1) //大于号
{
int xj=g3/3*3+(j-1)/3+1,yj=g3%3*3+(j-1)%3+1;
if(a[xj][yj]!=0)
if(i<a[xj][yj]) {
bl=1; break;
}
}
if(f[g3][ii][j]==2) //小于号
{
int xj=g3/3*3+(j-1)/3+1,yj=g3%3*3+(j-1)%3+1;
if(a[xj][yj]!=0)
if(i>a[xj][yj]){
bl=1; break;
}
}
}
if(bl==1) continue;
g[g3][i]=1;h[x][i]=1;l[y][i]=1; //将行，列，小九宫格标记为已选
a[x][y]=i; //标记选好的数字
dfs(x,y+1); //搜索下一个点
a[x][y]=0;
g[g3][i]=0;h[x][i]=0;l[y][i]=0; //回溯
}
}
int main()
{
int ci=0;
char s;
FOR(i,1,3) //把读入分为3组
{
FOR(k,1,5) //每组读入5行
{
if(k%2==1)
{
FOR(j,1,6) //单数行读入6个">"或"<"
{
int q1=(i-1)*3,q2=(j-1)/2,q3=q1+q2; //计算该符号属于哪一组小九宫格
cin>>s;
if(s=='>')
{
int qq=(k-1)/2*3+(j-1)%2+1;
f[q3][qq][qq+1]=1; //1为大于，2为小于
f[q3][qq+1][qq]=2;
}
else
{
int qq=(k-1)/2*3+(j-1)%2+1;
f[q3][qq][qq+1]=2;
f[q3][qq+1][qq]=1;
}
}
}
else
{
FOR(j,1,9) //双数行读入9个"v"或"^" 以下步骤与单数行相似
{
int q1=(i-1)*3,q2=(j-1)/3,q3=q1+q2;
cin>>s;
if(s=='v')
{
int qq=(k-1)/2*3+(j-1)%3+1;
f[q3][qq][qq+3]=1;
f[q3][qq+3][qq]=2;
}
else
{
int qq=(k-1)/2*3+(j-1)%3+1;
f[q3][qq][qq+3]=2;
f[q3][qq+3][qq]=1;
}
}
}
}
}
dfs(1,1);
return 0; //功德圆满
}
```