题目大意:判断一个数独游戏的谜题是否合法,即检查每行,每列,以及每个九宫格中是否有重复数字。

题目描述

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 '.'.

alter text

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.

算法描述

该题只需要让我们检查题面是否合法,不需要去求该数独谜题的解。

所以我们只需要按照数独游戏的规则,检查每一行,每一列,每一个小的九宫格是否有出现相同的数字即可。

代码

class Solution {
    bool myHash[9];
    void setHash() {
        memset(myHash, 0, sizeof(myHash));
        return ;
    }
    bool isExist(int x) {
        if (myHash[x]) return true;
        myHash[x] = true;
        return false;
    }
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // row
        for (int i = 0; i < 9; ++i) {
            setHash();
            for (int j = 0; j < 9; ++j)
                if (board[i][j] != '.') {
                    if (isExist(board[i][j] - '1')) return false;
                }
        }
        // column
        for (int j = 0; j < 9; ++j) {
            setHash();
            for (int i = 0; i < 9; ++i)
                if (board[i][j] != '.') {
                    if (isExist(board[i][j] - '1')) return false;
                }
        }
        // 3x3
        for (int x = 0; x < 9; x += 3)
            for (int y = 0; y < 9; y += 3) {
                setHash();
                for (int i = 0; i < 3; ++i)
                    for (int j = 0; j < 3; ++j)
                        if (board[i + x][j + y] != '.') {
                            if (isExist(board[i + x][j + y] - '1')) return false;
                        }
            }
        return true;
    }
};

登录发表评论 注册

反馈意见