Search-Hard

Abstract： 搜索 Hard 合集

51. N-Queens

解法一：dfs回溯

标准回溯法

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        string s;
        for(int i = 0; i < n; ++i) s += '.';
        vector<string> board(n, s);
        vector<vector<string>> res;
        dfs(board, 0, res);
        return res;
    }

    void dfs(vector<string>& board, int row, vector<vector<string>>& res) {
        if(row >= board.size()) {
            res.push_back(board);
            return;
        }
        for(int i = 0; i < board[row].size(); ++i) {
            if(isValid(board, row, i)) {
                board[row][i] = 'Q';
                dfs(board, row + 1, res);
                board[row][i] = '.';
            }
        } 
            
    }

    bool isValid(const vector<string>& board, int r, int c) {
        int row = board.size(), col = board[0].size();
        for(int i = 1; i <= r; ++i) {
            if(c - i > -1 && board[r][c - i] == 'Q') return false;
            if(r - i > -1 && board[r - i][c] == 'Q') return false;
            if(c - i > -1 && r - i > -1 && board[r - i][c - i] == 'Q') return false;
            if(c + i < col && r - i > -1 && board[r - i][c + i] == 'Q') return false;
        }
        return true;
    }
};

解法二：状压优化

前提是n小于等于32，当然如果用long long 的话可以到64