LeetCode 37.解数独

37. 解数独

class Solution {
    
public:
    void solveSudoku(vector<vector<char>>& board) {
    
        pair<int,int> p = getNext(board);
        int sx = p.first,sy = p.second;
        dfs(sx,sy,board);
    }
    bool dfs(int x,int y,vector<vector<char>>& board){
    
        if(isFinished(board)) {
    
            return true;
        }
        for(int n=1;n<=9;n++){
    
            board[x][y] = char(n+'0');
            if(isValidSudoku(board)){
    
                pair<int,int> p = getNext(board);
                int sx = p.first,sy = p.second;
                if(dfs(sx,sy,board)){
    
                    return true;
                }
            } 
        }
        board[x][y] = '.';
        return false;
    }

    pair<int,int> getNext(vector<vector<char>>& board) {
    
        int sx=-1,sy=-1;
        for(int i=0;i<9;i++){
    
            if(sx!=-1){
    
                break;
            }
            for(int j=0;j<9;j++){
    
                if(board[i][j]=='.'){
    
                    sx = i, sy = j;
                    break;
                }
            }
        }   
        return make_pair(sx,sy);     
    }

    bool isFinished(vector<vector<char>>& board){
    
        for(int i=0;i<9;i++){
    
            for(int j=0;j<9;j++){
    
                if(board[i][j]=='.'){
    
                    return false;
                }
            }
        }
        return true;
    }
    bool isValidSudoku(vector<vector<char>>& board) {
    
        bool rv[9][10]={
    0},cv[9][10]={
    0},gv[9][10]={
    0};
        for(int i=0;i<9;i++){
    
            for(int j=0;j<9;j++){
    
                if(board[i][j]=='.') {
    
                    continue;
                }
                int v = board[i][j]-'0';
                if(rv[i][v] || cv[j][v] || gv[i/3*3+j/3][v]){
    
                    return false;
                }
                rv[i][v] = 1;
                cv[j][v] = 1;
                gv[ i/3*3+j/3 ][v] = 1;
            }
        }
        return true;        
    }    
};