[LeetCode][Hard] 51. N-Queens

Leetcode 網址: https://leetcode.com/problems/n-queens/

題目說明:

知名的 n 皇后問題，請找出 n 皇后的所有解。

解題說明:

使用 DFS 去窮舉出所有 n 皇后的解。

程式碼

class Solution {
public:
    int flag[9] = {0};
    vector<vector<string>> answers;
    
    bool isValid(vector<string>& board, int row, int col) {
        for (int i = 0; i < 9 && flag[i]; i++) {
            if (flag[i] == col) return false;
            if (flag[i] + i == row + col) return false;
            if (row - i == col - flag[i]) return false;
        }
        return true;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(board, 0, n);
        return answers;
    }
    
    void dfs(vector<string>& board, int row, int n) {
        if (row == n) {
            answers.push_back(board);
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (!isValid(board, row, i + 1)) continue;
            flag[row] = i + 1;
            board[row][i] = 'Q';
            dfs(board, row + 1, n);
            board[row][i] = '.';
            flag[row] = 0;
        }
    }
};

結果

Runtime: 4 ms, faster than 94.91% of C++ online submissions for N-Queens.

Memory Usage: 7.4 MB, less than 76.70% of C++ online submissions for N-Queens.