leetcode 51N皇后 52N皇后II

朱雀 2023-06-19 09:43 203阅读 0赞

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:  
![在这里插入图片描述][format_png]

输入: 4  
输出: \[  
\[".Q…", // 解法 1  
“…Q”,  
“Q…”,  
“…Q.”\],

\["…Q.", // 解法 2  
“Q…”,  
“…Q”,  
“.Q…”\]  
\]  
解释: 4 皇后问题存在两个不同的解法。

思路： 回溯即可，回溯每一行，只是每填充一个Q，需要判断放入是否冲突了。

class Solution {
        
        int n = 0;
        public  List<List<String>> solveNQueens(int n) {
        
            List<List<String>> list = new ArrayList<>();
            if (n <= 0) {
        
                return list;
            }
            this.n = n;
    
            char[][] chars = new char[n][n];
            for (int i = 0;i < n;i++) {
        
                for (int j = 0;j < n;j++) {
        
                    chars[i][j] = '.';
                }
            }
            dfs(list,chars,0);
            return list;
        }
    
         public  void dfs (List<List<String>> list,char[][] chars,int start) {
        
    
            if (start  == this.n ) {
        
                List<String> tmp = new ArrayList<>();
                for (int i = 0;i < this.n;i++) {
        
                    tmp.add(new String(chars[i]));
                }
                list.add(tmp);
                return;
            }
    
            for (int i = 0;i < n;i++) {
        
                chars[start][i] = 'Q';
                if (isExist(chars,start,i)) {
        
                    dfs(list,chars,start+1);
                }
                chars[start][i] = '.';
            }
        }
    
    
       public  boolean isExist(char[][] chars,int row,int col) {
        
    
            for (int i = 0;i < col;i++) {
        
                if (chars[row][i] == 'Q') return false;
            }
            for (int i = 0; i < row;i++) {
        
                if (chars[i][col] == 'Q') return false;
            }
            int j = col-1;
            for (int i = row-1;i >= 0 && j >= 0 ;) {
        
                if (chars[i][j] == 'Q') return false;
                i--;
                j--;
            }
            j = col+1;
            for (int i = row-1;i >= 0 && j < this.n; ) {
        
                if (chars[i][j] == 'Q') return false;
                i--;
                j++;
            }
            return true;
        }
    }

leetcode 52 增加一个全局变量即可

class Solution {
        
        int n = 0;
        int count = 0;
        public int totalNQueens(int n) {
        
        
            if (n <= 0) {
        
                return count;
            }
            this.n = n;
    
            char[][] chars = new char[n][n];
            for (int i = 0;i < n;i++) {
        
                for (int j = 0;j < n;j++) {
        
                    chars[i][j] = '.';
                }
            }
            dfs(chars,0);
            return count;
        }
    
         public  void dfs (char[][] chars,int start) {
        
    
            if (start  == this.n ) {
        
                this.count++;
                return;
            }
    
            for (int i = 0;i < n;i++) {
        
                chars[start][i] = 'Q';
                if (isExist(chars,start,i)) {
        
                    dfs(chars,start+1);
                }
                chars[start][i] = '.';
            }
        }
    
    
       public  boolean isExist(char[][] chars,int row,int col) {
        
    
            for (int i = 0;i < col;i++) {
        
                if (chars[row][i] == 'Q') return false;
            }
            for (int i = 0; i < row;i++) {
        
                if (chars[i][col] == 'Q') return false;
            }
            int j = col-1;
            for (int i = row-1;i >= 0 && j >= 0 ;) {
        
                if (chars[i][j] == 'Q') return false;
                i--;
                j--;
            }
            j = col+1;
            for (int i = row-1;i >= 0 && j < this.n; ) {
        
                if (chars[i][j] == 'Q') return false;
                i--;
                j++;
            }
            return true;
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE4LzEwLzEyLzgtcXVlZW5zLnBuZw?x-oss-process=image/format,png