ACM学习历程—UESTC 1222 Sudoku（矩阵）(2015CCPC H)-白红宇

ACM学习历程—UESTC 1222 Sudoku（矩阵）(2015CCPC H)

阅读量：5049 次

发布时间：2019-06-12

本文共 1902 字，大约阅读时间需要 6 分钟。

题目链接：http://acm.uestc.edu.cn/#/problem/show/1226

题目大意就是构造一个行列和每个角的2*2都是1234的4*4矩阵。

用dfs暴力搜索，不过需要每一步进行判断是否已经出现了重复，如果最后再判断的话复杂度有点高。

代码:

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #define LL long longusing namespace std;char str[5][5];int a[5][5];bool vis[5];bool flag;bool judge(int x[][5]){ for (int i = 0; i < 4; ++i) { memset(vis, false, sizeof(vis)); for (int j = 0; j < 4; ++j) { if (!x[i][j]) continue; if (vis[x[i][j]]) return false; else vis[x[i][j]] = true; } } for (int j = 0; j < 4; ++j) { memset(vis, false, sizeof(vis)); for (int i = 0; i < 4; ++i) { if (!x[i][j]) continue; if (vis[x[i][j]]) return false; else vis[x[i][j]] = true; } } for (int i = 0; i <= 2; i += 2) { for (int j = 0; j <= 2; j += 2) { memset(vis, false, sizeof(vis)); for (int xx = 0; xx <= 1; xx++) { for (int yy = 0; yy <= 1; yy++) { if (!x[i+xx][j+yy]) continue; if (vis[x[i+xx][j+yy]]) return false; else vis[x[i+xx][j+yy]] = true; } } } } return true;}void input(){ for (int i = 0; i < 4; ++i) { scanf("%s", str[i]); for (int j = 0; j < 4; ++j) { if (str[i][j] == '*') a[i][j] = 0; else a[i][j] = str[i][j]-'0'; } }}void dfs(int i, int j){ if (flag) return; i += j/4; j %= 4; if (i == 4) { if (judge(a)) { for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) printf("%d", a[i][j]); printf("\n"); } flag = true; } return; } if (!judge(a)) return; if (!a[i][j]) { for (int x = 1; x <= 4; ++x) { a[i][j] = x; dfs(i, j+1); a[i][j] = 0; } } else dfs(i, j+1);}void work(){ flag = false; dfs(0, 0);}int main(){ //freopen("test.in", "r", stdin); int T; scanf("%d", &T); for (int times = 1; times <= T; ++times) { printf("Case #%d:\n", times); input(); work(); } return 0;}