[leetcode] 20. 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.

又是一開始犯了審題錯誤的毛病，我以為是要寫出一個計算數獨的AI，還在想為啥這種難度都被認為成簡單，結果我們看最後的note：

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

就是說不需要這個數獨是可以解，隻要判斷給你的這個數獨題目是不是合法的數獨就行了。是以難度就驟降了，随便找了一個解法上去AC。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        vector<vector<int>> bucket(3, vector<int>(9, 0));
         for (int i = 0; i < 9; i++)
         {
             for (int j = 0; j < 9; j++)
             {
                 if (board[i][j] != '.' && ++bucket[0][board[i][j] - '1'] > 1) return false;
                 if (board[j][i] != '.' && ++bucket[1][board[j][i] - '1'] > 1) return false;
                 int v = j%3 + 3*(i%3);
                 int h = j/3 + 3*(i/3);
                 if (board[v][h] != '.' && ++bucket[2][board[v][h] - '1'] > 1) return false;
             }
             bucket = vector<vector<int>>(3, vector<int>(9, 0));
         }
    }
};
           

每個點的合法性判斷有三種，一種是橫向是否有相同數字，一種是縱向是否有相同數字，一種是這個點所在的3*3格子内是否用相同數字。

轉載于:https://www.cnblogs.com/TinyBox/p/4137550.html