题目链接。
题目大意：
就是数独游戏。横竖，每一个9宫方块，必须有1~9，且不重复。
分析：
直接DFS。一开始在原图上搜，会TLE。把要补全的空格，放入数组，这样就不用遍历整个图寻找要填的空格了。
row, col, sq分别标记行，列，3*3方格是否重复。
话说，直接做
有人说反着搜（正着搜的意思就是从0~cnt-1，反着搜就是从cnt~0），试了试。
AC代码如下：
#include <cstdio>
#include <iostream>
#include <map>
#include <cstring> using namespace std; struct node {
int x, y;
}q[*+]; bool row[][], col[][], sq[][][];
int G[][], cnt; bool dfs(int cn) {
if(cn < ) return true; int x = q[cn].x, y = q[cn].y; for(int k=; k<=; k++) {
if(row[x][k] || col[y][k] || sq[x/][y/][k]) continue;
row[x][k] = col[y][k] = sq[x/][y/][k] = true; G[x][y] = k;
if(dfs(cn-)) return true; row[x][k] = col[y][k] = sq[x/][y/][k] = false;
} return false;
} int main() {
int T;
scanf("%d", &T); while(T--) {
cnt = ;
memset(row, false, sizeof(row));
memset(col, false, sizeof(col));
memset(sq, false, sizeof(sq)); for(int i=; i<; i++) {
for(int j=; j<; j++) {
scanf("%1d", &G[i][j]);
int k = G[i][j];
if(k != ) {
row[i][k] = col[j][k] = sq[i/][j/][k] = true;
}
else q[cnt++] = (node){i, j};
}
} dfs(cnt-); for(int i=; i<; i++) {
for(int j=; j<; j++) {
printf("%d", G[i][j]);
}
putchar('\n');
}
} return ;
}