leetcode 36：有效的數獨

題目傳送門

判斷一個 9x9 的數獨是否有效。隻需要根據以下規則，驗證已經填入的數字是否有效即可。

數字 1-9 在每一行隻能出現一次。

數字 1-9 在每一列隻能出現一次。

數字 1-9 在每一個以粗實線分隔的 3x3 宮内隻能出現一次。

上圖是一個部分填充的有效的數獨。

數獨部分空格内已填入了數字，空白格用 ‘.’ 表示。

示例 1:

輸入:

[

[“5”,“3”,".",".",“7”,".",".",".","."],

[“6”,".",".",“1”,“9”,“5”,".",".","."],

[".",“9”,“8”,".",".",".",".",“6”,"."],

[“8”,".",".",".",“6”,".",".",".",“3”],

[“4”,".",".",“8”,".",“3”,".",".",“1”],

[“7”,".",".",".",“2”,".",".",".",“6”],

[".",“6”,".",".",".",".",“2”,“8”,"."],

[".",".",".",“4”,“1”,“9”,".",".",“5”],

[".",".",".",".",“8”,".",".",“7”,“9”]

]

輸出: true

示例 2:

輸入:

[

[“8”,“3”,".",".",“7”,".",".",".","."],

[“6”,".",".",“1”,“9”,“5”,".",".","."],

[".",“9”,“8”,".",".",".",".",“6”,"."],

[“8”,".",".",".",“6”,".",".",".",“3”],

[“4”,".",".",“8”,".",“3”,".",".",“1”],

[“7”,".",".",".",“2”,".",".",".",“6”],

[".",“6”,".",".",".",".",“2”,“8”,"."],

[".",".",".",“4”,“1”,“9”,".",".",“5”],

[".",".",".",".",“8”,".",".",“7”,“9”]

]

輸出: false

解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格内其他數字均與 示例1 相同。

但由于位于左上角的 3x3 宮内有兩個 8 存在, 是以這個數獨是無效的。

說明:

一個有效的數獨（部分已被填充）不一定是可解的。

隻需要根據以上規則，驗證已經填入的數字是否有效即可。

給定數獨序列隻包含數字 1-9 和字元 ‘.’ 。

給定數獨永遠是 9x9 形式的。

思路：按照題目要求，一行不能有同樣的數字，一列不能有同樣的數字，3*3小方格也不能有相同的數字。是以我們可以用一個二維布爾變量數組a[i][j],表示目前行或者列中j有沒有出現過，結果為true時說明不符合數獨規則，輸出false，如果為false時說明j第一次在本行或者列出現，将a[i][j]設為true，繼續判斷。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        if(board.size()==0)  return false;
        else
        {
         vector<vector<bool>> row(9,vector<bool>(9,false));
         vector<vector<bool>> col(9,vector<bool>(9,false));
         vector<vector<bool>> cell(9,vector<bool>(9,false));
         for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
               if(board[i][j]>='0'&&board[i][j]<='9')
               {
                   int num=board[i][j]-'1';
                   if(row[i][num]||col[num][j]||cell[3*(i/3)+j/3][num])//小的3*3子產品依次從左到右從上到下編号
                      return false;
                    row[i][num]=true;
                    col[num][j]=true;
                   cell[3*(i/3)+j/3][num]=true;
               }
            }
            return true;
        }
    }
};