Clear C++ solution super easy to understand 12ms


  • 0
    M
    int GRID_SIZE;
    bool check_valid(vector<int> &columns, int row1, int col1) {
        for (int row2 = 0; row2 < row1; row2++) {
            int col2 = columns[row2];
            if (col1 == col2) {
                return false;
            }
            int col_distance = abs(col2 - col1);
            int row_distance = row1 - row2;
            if (col_distance == row_distance) {
                return false;
            }
        }
        return true;
    }
    void place_queen(int row, vector<int> &columns, vector<vector<string>> &res) {
        if (row == GRID_SIZE) {
            vector<string> cur_sol(GRID_SIZE, string(GRID_SIZE, '.'));
            for (int i = 0; i < GRID_SIZE; i++) {
                cur_sol[i][columns[i]] = 'Q';
            }
            res.push_back(cur_sol);
           
        } else {
            for (int col = 0; col < GRID_SIZE; col++) {
              
                if (check_valid(columns, row, col)) {
                    
                    columns[row] = col;
                    place_queen(row + 1, columns, res);
                   
                }
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        GRID_SIZE = n;
        vector<vector<string>> res;
        if (n <= 0) return res;
        vector<int> columns(n);
       
        place_queen(0, columns, res);
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.