poj 2676 Sudoku ( dfs )

dfs 用的还是不行啊，做题还是得看别人的博客！！！

题目：http://poj.org/problem?id=2676

题意：把一个9行9列的网格，再细分为9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。

0是待填位置，其他均为已填入的数字。

要求填完九宫格并输出（如果有多种结果，则只需输出其中一种）

如果给定的九宫格无法按要求填出来，则输出原来所输入的未填的九宫格

参考博客：http://www.cnblogs.com/tanhehe/archive/2013/08/07/3243073.html

http://blog.csdn.net/lyy289065406/article/details/6647977

r、c、g数组用来剪枝

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<stack>
 6 #include<queue>
 7 #include<iomanip>
 8 #include<cmath>
 9 #include<map>
10 #include<vector>
11 #include<algorithm>
12 using namespace std;
13 
14 struct node
15 {
16     int x,y;
17 }q[100];
18 int r[10][10],c[10][10],g[4][4][10];
19 int G[10][10],cnt;
20 
21 int dfs(int cn) //表示dfs 递归还是不太会
22 {
23     int x,y;
24     if(cn<0)  return 1;
25     x=q[cn].x; y=q[cn].y;
26     for(int k=1; k<=9; k++)
27     {
28         if(r[x][k] || c[y][k] || g[x/3][y/3][k]) continue;
29         r[x][k]=c[y][k]=g[x/3][y/3][k]=1;
30         G[x][y]=k;
31         if(dfs(cn-1)) return 1;
32         r[x][k]=c[y][k]=g[x/3][y/3][k]=0;
33     }
34     return 0;
35 }
36 int main()
37 {
38     int t,k;
39     cin>>t;
40     while(t--)
41     {
42         cnt=0;
43         memset(r,0,sizeof(r));
44         memset(c,0,sizeof(c));
45         memset(g,0,sizeof(g));
46         for(int i=0; i<9; i++)
47         {
48             for(int j=0; j<9; j++)
49             {
50                 scanf("%1d",&G[i][j]); //每次输入一个整数
51                 k=G[i][j];
52                 if(k!=0)
53                 r[i][k]=c[j][k]=g[i/3][j/3][k]=1; //g数组，每个子网格里是一样的
54                 else
55                 q[cnt++]=(node){i,j}; //赋值到结构体里，学习了
56             }
57         }
58         dfs(cnt-1);
59         for(int i=0; i<9; i++)
60         {
61             for(int j=0; j<9; j++)
62             cout<<G[i][j];
63             printf("
");
64         }
65     }
66     return 0;
67 }