在家别憋坏了,写个题运动一下。
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[]; 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; } } } }
|