HDU

Description

Yi Sima was one of the best counselors of Cao Cao. He likes to play a funny game himself. It looks like the modern Sudoku, but smaller.

Actually, Yi Sima was playing it different. First of all, he tried to generate a

Input

The first line of the input gives the number of test cases,

Output

For each test case, output one line containing Case #x:, where

Sample Input
3
****
2341
4123
3214
*243
*312
*421
*134
*41*
**3*
2*41
4*2*
Sample Output
Case #1:
1432
2341
4123
3214
Case #2:
1243
4312
3421
2134
Case #3:
3412
1234
2341
4123

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5547

The 2015 China Collegiate Programming Contest

***********************************************

分析：一道比较简单的数独题目，这里简化了问题，变成了一个4*4的图，然后小图变成了2*2的图，这里问题就简洁了很多。

地图辣么小，直接枚举每一个点就行了。

从左上角开始，一直枚举到右下角，然后输出了就行了。

每次遇到一个“*”我们就枚举他变成1,2,3,4然后判断是否合法，如果合法就进行下一个点，否则回溯。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<time.h>
 7 #include<stack>
 8 using namespace std;
 9 #define N 120000
10 #define INF 0x3f3f3f3f
11 
12 char a[120][120];
13 
14 int judge(int x,int y)
15 {
16     int i,j;
17 
18     for(i=0;i<4;i++)///列判断，不能有相同的数字
19     if(a[x][i]==a[x][y]&&i!=y)
20     return 0;
21 
22     for(i=0;i<4;i++)///行判断，不能有相同的数字
23     if(a[i][y]==a[x][y]&&i!=x)
24         return 0;
25 
26     int row=x;
27     int col=y;
28     if(x%2==1)x-=1;///找到小矩阵的左上角
29     if(y%2==1)y-=1;
30 
31     for(i=x;i<=x+1;i++)///小矩阵判断，不能有相同的数字
32         for(j=y;j<=y+1;j++)
33         if(a[i][j]==a[row][col]&&i!=row&&j!=col)
34         return 0;
35 
36     return 1;
37 }
38 
39 void dfs(int x)///回溯dfs
40 {
41     int i,j;
42 
43     if(x==4*4)///如果遍历了所有点，就输出最终图形
44     {
45         for(i=0;i<4;i++)
46         {
47             for(j=0;j<4;j++)
48                 printf("%c", a[i][j]);
49                 printf("
");
50         }
51         return ;
52     }
53 
54     int row=x/4;///行的计算方法
55     int col=x%4;///列的计算方法
56 
57     if(a[row][col]=='*')
58     {
59         for(j=1;j<=4;j++)///枚举4个数字
60         {
61             a[row][col]=j+'0';
62             if(judge(row,col))///如果当前这个点符合规则
63                 dfs(x+1);///进行下一步
64             a[row][col]='*';///记得要取消标记。（深搜尝试问题，涉及回溯）
65         }
66     }
67     else///如果不是，跳过，进行下一步
68         dfs(x+1);
69 }
70 
71 int main()
72 {
73     int T,k=1,i;
74 
75     scanf("%d", &T);
76 
77     while(T--)
78     {
79       for(i=0;i<4;i++)
80         scanf("%s", a[i]);
81 
82       printf("Case #%d:
", k++);
83 
84       dfs(0);
85     }
86     return 0;
87 }