LeetCode算法题（36）

36、有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku

思路

简单的方法是每行每列每个小九宫格都遍历一遍，总共遍历3遍。

进一步的方法是遍历一遍，对每个数字同时检验他在该行、该列、该小九宫格的有效性。

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
   //行，列，小方块
    int row[9][10], area[9][10], column[9][10];
    int i, j, dos,  num;
    for(i = 0; i < 9; i++)
    {
       memset(row[i], 0, sizeof(row[i]));
       memset(column[i], 0, sizeof(column[i]));
       memset(area[i], 0, sizeof(area[i]));
    }
    for(i = 0; i < 9; i++)
    {
       for( j = 0; j < 9; j++)
       {
           if(board[i][j] == '.')  continue;
            num = board[i][j] - '0';
            dos = i/3 * 3+ j/3;
            
            if(row[i][num] != 0|| column[j][num] != 0|| area[dos][num] != 0)  return false;
            row[i][num] ++;
            column[j][num] ++;
            area[dos][num]++;
            
       }
    }
    return true;
}