一道搜索写一天……我太菜了

在这篇题解里你可以看到

• 很多奇怪的式子

• 很多 if - 很多循环

（以上都是废话）

正文

解法大体就是 DFS + 判断，DFS填数独很简单，所以重点在于如何判断，本篇题解会重点讲解关于本题中判断的各类细节。

• DFS框架

从左上角$(1,1)$开始，自左向右，自上到下进行搜索。

自左向右好说，每次将 $y$ 加 $1$。自上到下就要换行，当 $y==10$ 时，已经出了$9*9$的数独范围，就要到下一行去，即 $x$ 加 $1$ ， $y=1$。

当搜索到$(9,10)$时搜索结束。

每到一个位置$(x,y)$，就枚举取值，然后根据各种条件判断当前位置是否可行。

• 判断

1. 普通数独的约束：每行、每列、每个子矩阵中取值不能重复。

我们可以开三个二维数组，第一维分别表示：每行、每列、每个子矩阵的编号，第二维表示$1\sim9$的取值。

例如：设二维数组 $vis1$ 来记录每行的取值情况，则 $vis1[i][j]=1$ 表示第 $i$ 行中已有数字 $j$ 。

2. 新数独的约束：每个子矩阵中四联通的大小规定。

首先要存下来大小规则，可以将输入看做三组，每组有五行，读入每组中的第 $x$ 行时根据 $x$的奇偶性判定读入几个字符。

字符读进来之后要进行一步转化方便使用。我们需要设一个四维数组 $f$，来存储大小关系。（可以像其他题解一样使用三维，但是四维无脑简单而且数据大小让我们可以任意搞）

$f[x][y][u][v]$中存储了矩阵中$(x,y)$和$(u,v)$的大小关系。

设二维数组 $a$ 存储最后的答案。

当$f[x][y][u][v]=1$时，$a[x][y]$ 应该小于 $a[u][v]$.

当$f[x][y][u][v]=2$时，$a[x][y]$ 应该大于 $a[u][v]$.

当$f[x][y][u][v]=0$时，$a[x][y]$ 与 $a[u][v]$ 的大小关系没有约束。

存下来之后就要用了。前面说了要在DFS枚举取值时判断当前枚举的值是否可行。

因为是四联通直接有约束，所以要将当前位置的当前取值与其左面和上面的取值进行比较，若符合他们之间的大小条件则搜索下一个位置，否则继续枚举。

与左面和上面进行判断的原因很简单，我们的搜索是自左向右，自上向下的，到搜索到$(x,y)$时，其四联通中只有左面 $(x,y-1)$ 和上面 $(x-1,y)$ 已有取值。

还有一个细节，就是子矩阵也是按照自左向右，自上向下进行编号的。

Before the Code

其实一开始的写法会T一个点，开 $O_2$才能过，在写这篇题解的时候又进行了几次改进，不吸氧的情况下最慢的点大致稳定在680ms左右。（我不是要故意占用评测姬资源的！）

一些坐标之间的转化并没有放到正文中，因为怕影响阅读体验，在代码当中进行了注释。如果第一眼看不明白可以随机找一个坐标代入手算一下帮助理解。如果发现了此篇题解中的错误或者想要交流欢迎私信和评论。

Enjoy the Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=11;
const int dx[]={0,1,1,1,4,4,4,7,7,7};//每个子矩阵的第一行在大矩阵中的行号
const int dy[]={0,1,4,7,1,4,7,1,4,7};//每个子矩阵的第一列在大矩阵中的列号
const int ddx[]={0,-1};//left down 
const int ddy[]={-1,0};
int a[maxn][maxn];//存储答案矩阵
char w[50];
int f[maxn][maxn][maxn][maxn];//存储大小关系
int vis1[maxn][maxn],flag;//关系1需要的三个数组和已找到答案的标记
int vis2[maxn][maxn];//数组分别是：每行、每列、每个子矩阵
int vis3[maxn][maxn];
void dfs(int x,int y)
{
	if(x==9&&y==10)//搜索已结束
	{
		for(int i=1;i<=9;i++)//输出答案
		{
			for(int j=1;j<=9;j++)
			printf("%d ",a[i][j]);
			printf("\n");
		}
		flag=1;//状态标记为搜索完成
		return ;
	}
	
	if(y==10)//需要换行
	{
		x++,y=1;
	}
	
	for(int i=1;i<=9;i++)//枚举取值
	{
		bool po=0;//记录当前取值是否满足条件，若不满足则更改为1
		int pos=((x/3+(x%3!=0))-1)*3+(y/3+(y%3!=0));//(x,y)所在子矩阵编号 
		
		if(vis1[x][i]||vis2[y][i]||vis3[pos][i])//条件1 
		continue;
		for(int j=0;j<=1;j++)//与左面和上面进行判断 
		{
			int xx=x+ddx[j];
			int yy=y+ddy[j];
			
			if(f[x][y][xx][yy]==1)//(x,y) < (xx,yy) 
			{
				if(i>a[xx][yy])//不符合条件
				{
					po=1;
					break;
				}	
			}
			if(f[x][y][xx][yy]==2)//(x,y) > (xx,yy)
			{
				if(i<a[xx][yy])//不符合条件
				{
					po=1;
					break;
				}
			}
		}
		if(po==1)//不符合条件，继续枚举
		continue;
        //更改标记和当前位置取值
		vis1[x][i]=1;
		vis2[y][i]=1;
		vis3[pos][i]=1;
		a[x][y]=i;
        
		dfs(x,y+1);//搜索下一个位置
        
		if(flag)//已完成搜索，返回
		return ;
        //回溯
		a[x][y]=0;
		vis1[x][i]=0;
		vis2[y][i]=0;
		vis3[pos][i]=0;
	}
}
int main(){
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=5;j++)
		{
			if(j%2)//每组中的奇数行为左右关系，读入6个
			{
				for(int k=1;k<=6;k++)
					cin>>w[k];//cin可以不读入空格和回车
			}else
			{//每组中的偶数行为上下关系，读入9个
				for(int k=1;k<=9;k++)
				cin>>w[k];
			}
			int x,y;
            //左右关系时让x为当前所在行编号
            //上下关系时让x为下面一行的编号
            x=(i-1)*3+(j/2)+1;
			if(j%2)
			{
				//6 左右关系
				y=1;//列编号
				for(int k=1;k<=6;k++)
				{
					int p1,p2;
					if(w[k]=='>')
					p1=2,p2=1;
					else
					p1=1,p2=2;
					if(y==3||y==6)//同子矩阵中才有条件
					y++;
					f[x][y][x][y+1]=p1;
					f[x][y+1][x][y]=p2;
					y++;
				}
			}else
			{
				//9 上下关系
				for(int k=1;k<=9;k++)
				{
					int p1,p2;
					if(w[k]=='v')
					p1=2,p2=1;
					else
					p1=1,p2=2;
					f[x-1][k][x][k]=p1;
					f[x][k][x-1][k]=p2;
				}
			}
		}
	}
	dfs(1,1);
	return 0;
} 

See Ya !