MyLeetcode/cpp_solutions/36.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
public:
    void fillFalse(vector<bool>& v) {
        for (int i = 0; i < 9; ++i) v[i] = false;
    }
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<bool> hash(9, false);
        // check row
        for (int i = 0; i < 9; ++i) {
            fillFalse(hash);
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                if (hash[board[i][j] - '1']) return false;
                hash[board[i][j] - '1'] = true;
            }
        }
        // check col
        for (int j = 0; j < 9; ++j) {
            fillFalse(hash);
            for (int i = 0; i < 9; ++i) {
                if (board[i][j] == '.') continue;
                if (hash[board[i][j] - '1']) return false;
                hash[board[i][j] - '1'] = true;
            }
        }
        // check grid
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                fillFalse(hash);
                for (int a = 0; a < 3; ++a) {
                    for (int b = 0; b < 3; ++b) {
                        if (board[i + a][j + b] == '.') continue;
                        if (hash[board[i + a][j + b] - '1']) return false;
                        hash[board[i + a][j + b] - '1'] = true;
                    }
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // check rows
        for (int i = 0; i < 9; ++i) {
            int mask = 0;
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '0';
                int val = 1 << num;
                if (mask & val) return false;
                mask |= val;
            }
        }
        // check cols
        for (int j = 0; j < 9; ++j) {
            int mask = 0;
            for (int i = 0; i < 9; ++i) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '0';
                int val = 1 << num;
                if (mask & val) return false;
                mask |= val;
            }
        }
        // check grids
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                int mask = 0;
                for (int r = i; r < i + 3; ++r) {
                    for (int c = j; c < j + 3; ++c) {
                        if (board[r][c] == '.') continue;
                        int num = board[r][c] - '0';
                        int val = 1 << num;
                        if (mask & val) return false;
                        mask |= val;
                    }
                }
            }
        }
        return true;
    }
};