leetcode 36

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

判断数独是否有效，即每一行数不能重复，每一列数不能重复，每个9宫格数不能重复。

思路比较简单，但在实现的过程中遇到一些麻烦。刚开始用最简单的比较法来判断数是否重复，结果运行时间超时。

后采用map容器，大大减少了判断重复的时间。

代码如下：

 1 class Solution {
 2 public:
 3     bool isValidSudoku(vector<vector<char>>& board) {
 4         int i,j,k,l,map[10];
 5         if(board.size()!=9 || board[0].size()!=9)
 6         {
 7             return false;
 8         }
 9         for(i=0;i<9;i++){
10             memset(map,0,sizeof(map));
11             for(j=0;j<9;j++){
12                 if(board[i][j]=='.')
13                 {
14                    continue; 
15                 }
16                 if(board[i][j]<'0' || board[i][j]>'9')
17                 {
18                     return false;
19                 }
20                 int num=board[i][j]-'0';
21                 if(map[num])
22                 {
23                     return false;
24                 }
25                 map[num]=1;
26             }
27         }
28         for(j=0;j<9;j++){
29             memset(map,0,sizeof(map));
30             for(i=0;i<9;i++){
31                 if(board[i][j]=='.')
32                 {
33                     continue;
34                 }
35                 int num=board[i][j]-'0';
36                 if(map[num])
37                 {
38                     return false;
39                 }
40                 map[num]=1;
41             }
42         }
43         for(i=0;i<9;i+=3){
44             for(j=0;j<9;j+=3){
45                 memset(map,0,sizeof(map));
46                 for(k=i;k<i+3;k++){
47                     for(l=j;l<j+3;l++){
48                         if(board[k][l]=='.')
49                         {
50                             continue;
51                         }
52                         int num=board[k][l]-'0';
53                         if(map[num])
54                         {
55                             return false;
56                         }
57                         map[num]=1;
58                     }
59                 }
60             }
61         }
62         return true;
63     }
64 };