8.6 补 dfs (UniquePathsII && N-Queens)

to do

10.3] Unique Paths II

    bool okToPlace(vector<string>& board, int row, int col) {
        // check cols
        for (int i=0; i<board.size(); ++i) {
            if (board[i][col]=='Q') return false;
        }
        // check upper diagnol on the left
        for (int i=row-1, j=col-1; i>=0 && j>=0; --i, --j) {
            if (board[i][j]=='Q') return false;
        }
        // check upper dignol on the right
        for (int i=row-1, j=col+1; i>=0 && j<board.size(); --i, ++j) {
            if (board[i][j]=='Q') return false;
        }
        return true;
    }
    
    void rec(vector<vector<string>>& ret, vector<string>& board, int n, int row) {
        if (row == n) {
            ret.push_back(board);
            return;
        }
        //traverse throught [i][0->n-1]
        for (int j=0; j<n; ++j) {
            if (okToPlace(board, row, j)) {
                board[row][j] = 'Q';
                rec(ret, board, n, row+1);
                board[row][j] = '.';
            }
        }
        
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<string> board (n, string(n, '.')) ;
        rec(ret, board, n, 0);
        return ret;
    }
};