HDU-1426 Sudoku Killer （技巧DFS）

题目传送门

思路：

一开始根本下不了手，有三个条件需要保证：
1.大矩阵的每一行都要包含1到9
2.大矩阵的每一列都要包含1到9
3.小矩阵包含着1到9的数字

实际上不需要先考虑这些条件，先把map建好然后写出dfs函数，然后再写一个judge函数来判断这三个条件就好了

技巧：

1.第一行第一列的字符需要判断一下，不然无法知道是否是测试用例数还是map的值

2.不能盲目的搜索，不然一定会TLE。需要先记录每个？的位置然后在每个？处用DFS来填充1到9的数字

注意：

judge里面的判断方法要理解掌握

此题最好用cin，cout，不然用scanf容易出问题

代码：

//有三个条件需要保证
//1.大矩阵的每一行都要包含1到9
//2.大矩阵的每一列都要包含1到9
//3.小矩阵包含着1到9的数字
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int num;                //记录？的个数 
int map[10][10];
struct node
{int x;int y;	
}a[100];bool judge(int x,int y,int k){for(int i=0;i<9;i++){   //判断该？上的行列是否有重复的数 if(map[i][y]==k)return false;if(map[x][i]==k)return false;			}int tem_x=(x/3)*3;    //关键步骤判断x,y所在第几个小九宫格中 int tem_y=(y/3)*3;for(int i=tem_x;i<tem_x+3;i++){for(int j=tem_y;j<tem_y+3;j++){if(map[i][j]==k)return false;}} return true;
}void dfs(int n){if(n==num){  //此时所有的？已经被填充，输出结果 for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(j<8)cout<<map[i][j]<<' ';elsecout<<map[i][j]<<endl;		} }return ;}for(int i=1;i<=9;i++)    //将1到9填充到？中 {if(judge(a[n].x,a[n].y,i)){map[a[n].x][a[n].y]=i;dfs(n+1);map[a[n].x][a[n].y]=0;} }return ;
} int main(){char s;int tem=0;while(cin>>s){num=0;if(s=='?') //特别判断第一个字符 ，用于输入多组字符{a[num].x=0;a[num].y=0;num++;map[0][0]=0;}elsemap[0][0]=s-'0';for(int i=0;i<9;i++)  //输入后八行 for(int j=0;j<9;j++){if(i==0 && j==0)continue; cin>>s;if(s=='?')    //需要记录下？的位置 {a[num].x=i;a[num].y=j;	num++;map[i][j]=0; } elsemap[i][j]=s-'0';}	if(tem++)	       //控制换行符 cout<<endl;dfs(0);	}return 0;	
}