[数据结构与算法]51. N 皇后

51. N 皇后

LeetCode刷题打卡第033天 _{（第1篇） 202100811}

题目链接

class Solution {
    public:
        vector<vector<string> > solveNQueens(int n) {
            //n皇后的意思就是任意两个点不同行，不同列，同时不会形成斜对角，所以就是每行每列一定只有一个，那个在n个不同的行不同的列
            vector<vector<string> > ans;
            vector<string> board(n,string(n,'.'));
            vector<bool>visited_col(n,false);   //判断本列是否已经被占用
            backtracking(ans,board,visited_col,n,0);
            return ans;
        }
        void backtracking(vector<vector<string> >&ans,vector<string> &board,vector<bool>& visited_col,int n,int row){   //一共有n行，因此只需要用pos记录当前在第几行
            if(row==n){
                ans.push_back(board);
                return;
            }
            for(int i=0;i<n;i++){
            if(!judge(board,visited_col,n,row,i)) continue;
                visited_col[i]=true;
                board[row][i]='Q';
                backtracking(ans,board,visited_col,n,row+1);
                visited_col[i]=false;
                board[row][i]='.';                                   
            }
        }
        bool judge(vector<string>& board,vector<bool>& visited_col,int n,int row,int col){
            if(visited_col[col]) return false;
            for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
                if (board[i][j] == 'Q') {
                    return false;
                }
            }
            for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (board[i][j] == 'Q') {
                    return false;
                }}
            
            return true;
        }
};