pyai's blog
0%

LeetCode 51.N皇后

Posted on Edited on In Views:

在家别憋坏了，写个题运动一下。

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

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

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

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

因为这个新型肺炎导致现在还没开学，现在只能每天躺床上了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    int L[], R[], col[], row[];//L和R标记两个对角线, col标记哪一列有皇后, row存储每一行的皇后在哪一列
    List<List<String>> list = new ArrayList<>();
    public void init(int n) {
        L = new int[n + n];
        R = new int[n + n];
        col = new int[n];
        row = new int[n];
    }
    public List<List<String>> solveNQueens(int n) {
        init(n);
        solve(0, n);
        return list;
    }
    public void solve(int cur_row, int n) {
        if(cur_row == n) { 
            List<String>cur_ans = new ArrayList<String>();
            for(int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < row[i]; j++) sb.append(".");
                sb.append("Q");
                for(int j = row[i] + 1; j < n; j++) sb.append(".");
                cur_ans.add(sb.toString());
            }
            list.add(cur_ans);
            return ;
        }
        for(int i = 0; i < n; i++) {
            if(col[i] == 0 && L[cur_row + i] == 0 && R[cur_row - i + n] == 0) {
                row[cur_row] = i; col[i] = 1; L[cur_row + i] = 1; R[cur_row - i + n] = 1;
                solve(cur_row + 1, n);
                col[i] = 0; L[cur_row + i] = 0; R[cur_row - i + n] = 0;
            }
        }
    }
}