Leetcode Valid Sudoku
9657 ワード
class Solution {
private:
// only used by _isValidSudoku
int row[9];
int col[9];
int blk[9];
public:
bool _isValidSudoku(vector<vector<char> >& board) {
if (board.empty()) return true;
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(blk, 0, sizeof(blk));
int rm, cm, bm;
for (int i=0; i<9; i++) {
int base = i / 3 * 3;
for (int j=0; j<9; j++) {
char ch = board[i][j];
if (ch == '.') continue;
int msk = 0x1<<(ch - '0');
int blk_idx = base + j / 3;
rm = msk|row[i];
cm = msk|col[j];
bm = msk|blk[blk_idx];
if (rm == row[i] || cm == col[j] || bm == blk[blk_idx]) {
return false;
}
row[i] = rm;
col[j] = cm;
blk[blk_idx] = bm;
}
}
return true;
}
bool isValidSudoku(vector<vector<char> >& board) {
if (board.empty()) return true;
int mx = board.size() - 1;
int my = board[0].size() - 1;
// each row
for (int i=0; i <= my; i++) {
if (!isValidRegion(board, 0, i, mx, 0)) return false;
}
// each column
for (int i=0; i <= mx; i++) {
if (!isValidRegion(board, i, 0, 0, my)) return false;
}
// each block
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++){
if (!isValidRegion(board, j*3, i*3, 2, 2)) return false;
}
}
return true;
}
bool isValidRegion(vector<vector<char> >& board, int sx, int sy, int dx, int dy) {
char count[10];
for (int i=0; i<10; i++) count[i] = 0;
for (int i=sy + dy; i >= sy; i--) {
for (int j=sx + dx; j >= sx; j--) {
char num = board[i][j];
if (num == '.') continue;
if (num > '9' || num < '0') return false;
if (++count[num-'0'] > 1) return false;
}
}
return true;
}
};
isValidSudoku常用方法で判断_isValidSudokuはビット演算で判断していますが、ここでもあまりアップグレードはありません