openjudge 2982--Sudoku(九宫格数独) DFS算法加剪枝

题目链接:http://bailian.openjudge.cn/practice/2982/

#include <iostream>
#include <cstring>
using namespace std;
int t[10][10];
bool flag;
bool ok=false;
void dfs(int m,int n){
	if(ok) return;
	if(m==9&&n==10){
		for(int i=1;i<10;++i){
			for(int j=1;j<10;++j){
				cout<<t[i][j];
			}
			cout<<endl;
		}
		ok=true;
		return;
	}else{
		if(n==10){
			dfs(m+1,0);
			return;
		}
		if(t[m][n]!=0){
			dfs(m,n+1);
			return;
		}

		for(int i=9;i>=1;--i){
			flag=true;
			for(int y=1;y<10;++y){
				if(t[m][y]==i){
					flag=false;
					break;
				}
			}
			if(flag){
				for(int x=1;x<10;++x){
					if(t[x][n]==i){
						flag=false;
						break;
					}
				}
			}

				
			if(flag){
				int pos_x,pos_y;
				if(m%3!=0){
					pos_x=(m/3)*3;
				}else{
					pos_x=m-3;
				}
				if(n%3!=0){
					pos_y=(n/3)*3;
				}else{
					pos_y=n-3;
				}
				for(int x=pos_x+1;x<=pos_x+3;++x){
					for(int y=pos_y+1;y<=pos_y+3;++y){
						if(t[x][y]==i){
							flag=false;
							goto X;
						}
					}
				}
			}

			X:
			if(flag==true){
				t[m][n]=i;
				dfs(m,n+1);
				if(ok) return;
				t[m][n]=0;
			}
		}
	}

}


void sudoku(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;
	cin>>n;
	char s[20][20];
	while(n--){
		ok=false;
		for(int i=0;i<9;++i){
			cin>>s[i];
		}
		for(int i=1;i<10;++i){
			for(int j=1;j<10;++j){
				t[i][j]=s[i-1][j-1]-'0';
			}
		}
		dfs(1,1);
	}

}

int main(){
	sudoku();
	return 0;
}