当前位置：首页 > news >正文

HDU 5547 Sudoku(DFS)

news 来源：原创 2024/5/20 22:02:00

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

题目：

Sudoku

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2372 Accepted Submission(s): 804

Problem 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

****

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

题意：

4*4的数独游戏，最终要凑成每行每列每个分块的值为1+2+3+4；即1-4每行每列每块不能重复出现。

思路：

用DFS做，将已经填的空数为判断标记，都填好即输出并返回。列和行比较好判断，至于分块，我定义了一个计算的方式：t=row*2/2+col(row和col都是从0开始的，t表示为第几个分块)。这样很明显，从左上角的4个小分块到右下角的4个小分块分别对应的就是0-3。

代码：

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 using namespace std;
 5 struct node{
 6     int r,c;
 7 };
 8 vector<node>v;
 9 char chess[10][10];
10 int col[10][10];//col[i][x]标记第i列 x数是否已经用过
11 int row[10][10];//row[i][x]标记第i行 x数是否已经用过
12 int block[10][10];//block[i][x]标记第i个分块，x数是否已经用过
13 int ok;
14 void dfs(int num){
15     if(ok)  return ;
16     if(num==v.size()){//所有数都填好
17         for (int i=0; i<4; i++) {
18             puts(chess[i]);
19         }
20         ok=1;
21         return ;
22     }
23     for(int i=1;i<=4;i++){
24         int r=v[num].r;
25         int c=v[num].c;
26         if(!col[c][i] && !row[r][i] && !block[r/2*2+c/2][i]){
27             chess[r][c]=i+'0';
28             col[c][i]=row[r][i]=1;
29             block[r/2*2+c/2][i]=1;
30             dfs(num+1);
31             col[c][i]=row[r][i]=0;//回溯还原状态
32             block[r/2*2+c/2][i]=0;
33             chess[r][c]='*';
34         }
35     }
36 }
37 int main(){
38     int t;
39     scanf("%d",&t);
40     for (int i=1; i<=t; i++) {
41         printf("Case #%d:\n",i);
42         v.clear();
43         memset(block, 0, sizeof(block));//初始值都为0，即都未用过
44         memset(col, 0, sizeof(col));
45         memset(row, 0, sizeof(row));
46         ok=0;
47         for (int j=0; j<4; j++) {
48             scanf("%s",chess[j]);
49             for (int k=0; k<4; k++) {
50                 if(chess[j][k]=='*'){//将需要填空的点放入vector容器
51                     node x;
52                     x.r=j;x.c=k;
53                     v.push_back(x);
54                 }else{
55                     int x=chess[j][k]-'0';//标记已经用过的点
56                     block[j/2*2+k/2][x]=1;
57                     row[j][x]=1;
58                     col[k][x]=1;
59                 }
60             }
61         }
62         dfs(0);//0表示在填空v[0]点
63     }
64     return 0;
65 }