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

LintCode_389 判断数独是否合法

news 来源：原创 2024/5/18 21:43:01

题目

请判定一个数独是否有效。

该数独可能只填充了部分数字，其中缺少的数字用 . 表示。

注意事项

一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。

说明

什么是 数独？

http://sudoku.com.au/TheRules.aspx
http://baike.baidu.com/subview/961/10842669.htm

样例

下列就是一个合法数独的样例。

Valid Sudoku

C++代码

 1  void clear(int *s, int n)
 2     {
 3         for(int i = 0; i < n; ++i)
 4             s[i] = 0;
 5     }
 6     bool rol_is_true(int s[], int n)
 7     {
 8         for(int i = 0; i < n; ++i)
 9         {
10             if(s[i] > 1) return false;
11         }
12         return true;
13     }
14     bool isValidSudoku(const vector<vector<char>>& board) {
15         //判断行
16         int s[10];
17         int i, j;
18         
19         for(i = 0; i < 9; ++i)
20         {
21             clear(s, 10);
22             for(j = 0; j < 9; ++j)
23             {
24                 if(board[i][j] != '.') s[board[i][j] - '0']++;
25             }
26             if(!rol_is_true(s, 10)) return false;
27         }
28         //判断列
29         for(i = 0; i < 9; ++i)
30         {
31             clear(s, 10);
32             for(j = 0; j < 9; ++j)
33             {
34                 if(board[j][i] != '.') s[board[j][i] - '0']++;
35             }
36             if(!rol_is_true(s, 10)) return false;
37         }
38         
39         //判断宫
40         int t,k,p;
41         for(t = 0, i = 0; i < 9; ++i)
42         {
43             if(i % 3 == 0) p = i;
44             clear(s, 10);
45             for(j = t; j < t + 3; ++j)
46             {
47                 for(k = p; k <p + 3; ++k)
48                 {
49                     if(board[j][k] != '.') s[board[j][k] - '0']++;
50                 }
51             }
52             if(!rol_is_true(s, 10)) return false;
53             t = (t + 3) % 9;
54         }
55         return true;
56     }