首页 > 其他 > 详细

Leetcode Valid Sudoku

时间:2014-03-12 22:54:58      阅读:540      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
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;
    }
};
bubuko.com,布布扣

isValidSudoku 使用常用方法判断
_isValidSudoku 使用位运算进行判断,不过这里也没什么提升

Leetcode Valid Sudoku,布布扣,bubuko.com

Leetcode Valid Sudoku

原文:http://www.cnblogs.com/lailailai/p/3597375.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!