ACM : POJ 2676 SudoKu DFS - 数独

#include"iostream"
#include"cstdio"
#include"cstring"
#include"queue"
#include"string"
using namespace std;
int map[11][11],count,n;
bool F[11][11];
bool H[11][11];
bool L[11][11];

struct Node {
	int x,y;
} node[100];

int MAP(int i,int j) {
	if(i<=3&&j<=3)return 1;
	else if(i<=3&&j<=6)return 2;
	else if(i<=3&&j<=9)return 3;
	else if(i<=6&&j<=3)return 4;
	else if(i<=6&&j<=6)return 5;
	else if(i<=6&&j<=9)return 6;
	else if(i<=9&&j<=3)return 7;
	else if(i<=9&&j<=6)return 8;
	else if(i<=9&&j<=9)return 9;
}

int  DFS(int n) {
	if(n>count) {
		return 1;
	}
	for(int j=1; j<=9; j++) {
		if(!H[node[n].x][j]&&!L[node[n].y][j]&&!F[MAP(node[n].x,node[n].y)][j]) {
			H[node[n].x][j]=L[node[n].y][j]=F[MAP(node[n].x,node[n].y)][j]=1;
			map[node[n].x][node[n].y]=j;
			if(DFS(n+1))return 1;
			H[node[n].x][j]=L[node[n].y][j]=F[MAP(node[n].x,node[n].y)][j]=0;
		}
	}
	return 0;
}


int main() {
	int flag=0;
	while(cin>>n) {
		for(int i=1; i<=n; i++) {
			memset(map,0,sizeof(map));
			memset(H,0,sizeof(H));
			memset(F,0,sizeof(F));
			memset(L,0,sizeof(L));
			count = 0;
			for(int j=1; j<=9; j++)
				for(int k=1; k<=9; k++) {
					scanf("%1d",&map[j][k]);
					if(map[j][k]==0) {
						count++;
						node[count].x=j;
						node[count].y=k;
					} else {
						H[j][map[j][k]]=1;
						L[k][map[j][k]]=1;
						F[MAP(j,k)][map[j][k]]=1;
					}
				}
			DFS(1);
			for(int j=1; j<=9; j++) {
				for(int k=1; k<=9; k++)
					cout<<map[j][k];
				cout<<endl;
			}

		}
	}
	return 0;
}