lt18/36.valid-sudoku.cpp at master · brewtiful/lt18 · 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
 * [36] Valid Sudoku
 *
 * https://leetcode.com/problems/valid-sudoku/description/
 *
 * algorithms
 * Medium (38.04%)
 * Total Accepted:    159K
 * Total Submissions: 417.3K
 * Testcase Example:  '[["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"]]'
 *
 * Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be
 * validated according to the following rules:
 *
 *
 * Each row must contain the digits 1-9 without repetition.
 * Each column must contain the digits 1-9 without repetition.
 * Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without
 * repetition.
 *
 *
 *
 * A partially filled sudoku which is valid.
 *
 * The Sudoku board could be partially filled, where empty cells are filled
 * with the character '.'.
 *
 * Example 1:
 *
 *
 * 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
 *
 *
 * Example 2:
 *
 *
 * Input:
 * [
 * ["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"]
 * ]
 * Output: false
 * Explanation: Same as Example 1, except with the 5 in the top left corner
 * being
 * ⁠   modified to 8. Since there are two 8's in the top left 3x3 sub-box, it
 * is invalid.
 *
 *
 * Note:
 *
 *
 * A Sudoku board (partially filled) could be valid but is not necessarily
 * solvable.
 * Only the filled cells need to be validated according to the mentioned
 * rules.
 * The given board contain only digits 1-9 and the character '.'.
 * The given board size is always 9x9.
 *
 *
 */
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
	if (!checkRow(board)) return false;
	if (!checkCol(board)) return false;
	if (!checkSub(board)) return false;
	return true;
    }
    bool checkRow(vector<vector<char>>& board) {
    	for (int i = 0; i < 9; i++) {
		vector<int> visited(9);
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == '.') continue;
			if (visited[board[i][j]-'0'-1]) return false;
			visited[board[i][j]-'0'-1] = 1;
		}
	}
	return true;
    }
    bool checkCol(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
                vector<int> visited(9);
                for (int j = 0; j < 9; j++) {
			if (board[j][i] == '.') continue;
                        if (visited[board[j][i]-'0'-1]) return false;
                        visited[board[j][i]-'0'-1] = 1;
                }
        }
        return true;
    }
    bool checkSub(vector<vector<char>>& board) {
    	for (int i = 0; i < 9; i += 3) {
		for (int j = 0; j < 9; j += 3) {
			vector<int> visited(9);
			for (int k = 0; k < 3; k++) {
				for (int t = 0; t < 3; t++) {
					if (board[i+k][j+t] == '.') continue;
					if (visited[board[i+k][j+t]-'0'-1]) return false;
					visited[board[i+k][j+t]-'0'-1] = 1;
				}
			}
		}
	}
	return true;
    }
};