做题感悟：第一次做时直接暴力就水过，但是在看别人解题报告时有人竟然用 0 ms 过了，很无语。
解题思路：1 ) 直接暴力 耗时大约：1400ms 2 ) 用三个标记数组标记 耗时大约：400ms
3 ) 用精确覆盖算法 耗时大约：0 ms ，但是倒着填数比正着填要耗时短一般为 16 ms 就过了，估计是数据问题。那就说一下第二种方法吧，第三种没接触：用三个数组 row[ ][ ] col[ ][ ] vis[ ][ ] 分别标记一个数在第几行，第几列，第几个小正方形出现过，于是查询的时候就是O( 1 ) 的复杂度,至于row col 好标记，至于列 用 i / 3 * 3 + j/ 3
就是第几格小正方形（找规律）。
代码（逆向）：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld __int64
const double PI = 3.1415926535898 ;
const int INF = 99999999 ;
const double esp = 1e-8 ;
const long long mod= 1000 ;
const int MX = 15 ;
bool flag ;
int g[MX][MX] ;
bool row[MX][MX],col[MX][MX],vis[MX][MX] ;
void dfs(int x,int y)
{
if(flag) return ;
if(y==-1)
{
x-- ;
y=8 ;
}
if(x==-1&&y==8)
{
for(int i=0 ;i<9 ;i++)
{
for(int j=0 ;j<9 ;j++)
printf("%d",g[i][j]) ;
printf("\n") ;
}
flag=true ;
return ;
}
if(g[x][y])
dfs(x,y-1) ;
else
{
for(int i=1 ;i<=9 ;i++)
if(!row[x][i]&&!col[y][i]&&!vis[3*(x/3)+y/3][i])
{
row[x][i]=true ;
col[y][i]=true ;
vis[3*(x/3)+y/3][i]=true ;
g[x][y]=i ;
dfs(x,y-1) ;
g[x][y]=0 ;
row[x][i]=false ;
col[y][i]=false ;
vis[3*(x/3)+y/3][i]=false ;
}
}
}
int main()
{
int Tx ;
char s[MX] ;
scanf("%d",&Tx) ;
while(Tx--)
{
memset(row,false,sizeof(vis)) ;
memset(col,false,sizeof(col)) ;
memset(g,0,sizeof(g)) ;
memset(vis,false,sizeof(vis)) ;
int k,x ;
for(int i=0 ;i<9 ;i++)
{
scanf("%s",s) ;
for(int j=0 ;j<9 ;j++)
{
g[i][j]=x=s[j]-'0' ;
if(x)
{
k=3*(i/3)+j/3 ;
row[i][x]=true ;
col[j][x]=true ;
vis[k][x]=true ;
}
}
}
flag=false ;
dfs(8,8) ;
}
return 0 ;
}