🌕 🌕 51. N 皇后

难度: 🌕 🌕

问题描述

---

解法

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        // 思路:
        int[][] dp = new int[n][n];
        mySol(n, dp, 0);
        return res;
    }

    private void mySol(int len, int[][] dp, int curRow) {
        // 递归终止条件
        if(curRow == len) {
            // 封装结果
            getRes(len, dp);
            return;
        }
        for(int j = 0; j < len;j ++) {
            if(isValid(len, dp, curRow, j)) {
                dp[curRow][j] = 1;
                mySol(len, dp, curRow + 1);
                dp[curRow][j] = 0;
            }
        }
    }

    private void getRes(int len, int[][] dp) {
        List<String> list = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < len; j ++) {
                if(dp[i][j] == 0) {
                    sb.append(".");
                } else {
                    sb.append("Q");
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }

    private boolean isValid(int len, int[][] dp, int curRow, int curCol) {
        // 判断当前点是否合适放入皇后
        // 从 该点出发，左上方 - 上方 - 右上方 均无皇后
        for(int i = curRow - 1, j = curCol - 1; i >= 0 && j >= 0; i --, j --) {
            if(dp[i][j] == 1) {
                return false;
            } 
        }
        for(int i = curRow; i >= 0; i --) {
            if(dp[i][curCol] == 1) {
                return false;
            }
        }
        for(int i = curRow - 1, j = curCol + 1; i >= 0 && j < len; i --, j ++) {
            if(dp[i][j] == 1) {
                return false;
            }
        }
        return true;
    }
}

---

输出