LeetCode 36. Valid Sudoku [Medium] [C++] 解題筆記

這題給我們一個玩到一半的 9 X 9 數獨，要我們判斷目前的結果是不是正確的(有沒有符合數獨的規定)。

EX:

        Input:

[
  ["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"]
]
    Output: true

想法:

    這題可以分別用三個二維陣列 row, col 和 box 分別紀錄每一列每一行與每一個九宮格中每個數字的使用情況，

然後就可以遍歷整個 board 來驗證是否符合數獨的規則，另外 box 對應的 index 可以透過當前的 row 跟 col 計算得出，

box_idx = (row / 3) * 3 + col / 3 。

完整程式碼:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<int>> row(9, vector<int>(10));
        vector<vector<int>> col(9, vector<int>(10));
        vector<vector<int>> box(9, vector<int>(10));
        
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == '.') { continue; }
                int n = board[i][j] - '0';
                int box_idx = (i / 3)*3 + j / 3;
                if (row[i][n] || col[j][n] || box[box_idx][n]) { return false; }
                row[i][n] = 1;
                col[j][n] = 1;
                box[box_idx][n] = 1;
            }
        }
        
        return true;
    }
};