Leetcode 51 N Queens

题意：给定一个数字$n$，形成n*n的棋盘，棋盘上放n个皇后，确保皇后之间不会相互吃（皇后可以直线吃，斜线吃）

https://leetcode.com/problems/n-queens/description/

题解：首先这是一道dfs，枚举所有可以放n皇后的地方。构造一个数组pos,$pos[i]$代表在第i行第j列放一个皇后。当数组满足长度要求时dfs结束。传入参数u表示当前我需要在第u行加入一个皇后，遍历所有n列，判断我皇后是否可以放入，如果可以放，那么就放，进入下一层dfs

class Solution {
public:
    vector<vector<string>> res; 
    vector<vector<string>> solveNQueens(int n) {
        //pos保证所有的n queens不可能在同一行，所以循环中只需要check
        //是不是同一列或者斜对角就可以
        vector<int> pos;
        dfs(0, pos, n);
        return res;
    }
    
    void dfs(int u, vector<int>& pos, int n) {
        if( u == n ) {
            vector<string> str(n, string(n, '.'));
            for(int i = 0; i < n; i++) {
                str[i][pos[i]] = 'Q';
            }
            res.push_back(str);
            return;
        }
        for(int i = 0; i < n; i++) {
            if(isValid(pos,u, i)) {
                pos.push_back(i);
                dfs(u+1, pos, n);
                pos.pop_back();
            }
        }
    }

    bool isValid(vector<int>& pos, int row, int col) {
        int m = pos.size();
        for(int i = 0; i < m; i++) {
            int preRow = i;
            int preCol = pos[i];
            if(col == preCol) return false;
            if(abs(row-preRow) == abs(col - preCol)) return false;
        }
        return true;
    }

};

时间复杂度：$O(N^2\ast N!)$ ？
空间复杂度：$O(N)$

原文地址：https://blog.csdn.net/xxxmmc/article/details/144016498

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！