leetcode 51 N皇后-蒲公英云

leetcode 51 N皇后

我就是我 2022-09-14 09:27 212阅读 0赞

前言

题目：51. N 皇后

参考题解：N皇后-代码随想录

提交代码

题目要求：任何两个皇后都不能处于同一条横行、纵行或斜线上。

思路：按行遍历放置。用回溯解决。

我实现的代码，在处理能否放置的问题上，搞复杂了。虽然它是正确的。

#include <vector>
#include <string>
#include <iostream>
#include <cassert>
#include <set>
using namespace std;
class Solution {
private:
    vector<string> chessboard;
    vector<vector<string>> result;
     // 二维表示棋盘；棋盘中每个格子为一个集合，里面放入哪个Q占用
    vector<vector<set<pair<int,int>>>> used;
public:
    bool Q_used(pair<int,int> loc, int cmd){
        // flag = 0, 放置一个Q，所占用其所在行，列，对角线
        // flag = 1, 拿走一个Q，所释放其所在行，列，对角线
        // flag = 2, 检查该位置，能否放置Q。true表示可以放置，false表示不可放置
        const int n = used.size();
        const int row = loc.first;
        const int col = loc.second;
        if(cmd == 0){
            for(int i=0; i<n; i++) // 所在行累计标记flag
                used[row][i].insert({row,col});
            for(int i=0; i<n; i++) // 所在列累计标记flag
                used[i][col].insert({row,col});
            for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) // 左上方对角线，累计标记flag
                used[i][j].insert({row,col});
            for(int i=row+1, j=col+1; i<n && j<n; i++, j++) // 右下方对角线，累计标记flag
                used[i][j].insert({row,col});
            for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++) // 右上方对角线，累计标记flag
                used[i][j].insert({row,col});
            for(int i=row+1, j=col-1; i<n && j>=0; i++, j--) // 右上方对角线，累计标记flag
                used[i][j].insert({row,col});
            return true;
        }else if(cmd == 1){
            for(int i=0; i<n; i++) 
                used[row][i].erase({row,col});
            for(int i=0; i<n; i++)
                used[i][col].erase({row,col});
            for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) 
                used[i][j].erase({row,col});
            for(int i=row+1, j=col+1; i<n && j<n; i++, j++) 
                used[i][j].erase({row,col});
            for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++)
                used[i][j].erase({row,col});
            for(int i=row+1, j=col-1; i<n && j>=0; i++, j--)
                used[i][j].erase({row,col});
            return true;
        }else if(cmd == 2){
            if(used[row][col].empty())
                return true;
            else
                return false;
        }else{
            cout<<"no such cmd"<<endl;
            exit(0);
        }
    }
    void backTracking(int start_row){
        // 出口之一： 当n*n的棋盘，成功放入n个Q
        if(start_row == used.size()){
            result.push_back(chessboard);
            return;
        }
        for(int i=0; i<used.size(); i++){
            if(Q_used({start_row,i},2) == false) // 检查{start_row,i}位置能否放入Q
                continue;
            Q_used({start_row,i},0); // 在{start_row,i}位置放入Q
            chessboard[start_row][i] = 'Q';
            backTracking(start_row+1); // 在下一行找合适的位置放置Q
            chessboard[start_row][i] = '.';
            Q_used({start_row,i},1); // 在{start_row,i}位置拿走Q
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        chessboard.resize(n,string(n,'.'));
        used.resize(n,vector<set<pair<int,int>>>(n,set<pair<int,int>>{}));
        backTracking(0);
        return result;
    }
};
int main(void){
    int n = 4;
    Solution s;
    vector<vector<string>> result = s.solveNQueens(6);
    for(auto one : result){
        for(auto str : one)
            cout<<str<<" ";
        cout<<endl;
    }
}

参考题解，在这方面做的更好。放置之前进行动态判断，不需要辅助空间。

下面代码来自参考题解。

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋牌的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    int count = 0;
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};