51. N 皇后 https://leetcode-cn.com/problems/n-queens/description/
啊, 经典的 N 皇后问题. 想当初高中练 NOIP 的时候, 这个题把我折磨了好久
经典的 dfs + 回溯问题
4 个约束条件, 题中没有明确指出 (并不是所有人都知道国际象棋的规则啊喂):
一个皇后在其横纵线与两条斜线上, 不能存在其它皇后.
我们来用 4 个数组来记录对应的 4 个约束状态 (其实 3 个就够了):
col[] 行
row[] 列
h[] 对角线
r[] 对角线
那么其 i,j 坐标关系可描述为
- col[i]
- row[j]
- h[i+j]
- r[i-j + n]
代码
- class Solution {
- public List<List<String>> solveNQueens(int n) {
- boolean[] row = new boolean[n];
- boolean[] h = new boolean[2 * n];
- boolean[] r = new boolean[2 * n];
- List<List<String>> ans = new ArrayList<>();
- dfs(n, row, h, r, new ArrayList<>(), 0, ans);
- return ans;
- }
- public void dfs(int n, boolean[] row, boolean[] h, boolean[] r, List<Integer> curList, int curK, List<List<String>> ans) {
- if (curK == n) {
- List<String> tmp = new ArrayList<>();
- for (Integer integer : curList) {
- String st = "";
- for (int i = 0; i < n; i++) {
- if (i == integer) {
- st += "Q";
- } else {
- st += ".";
- }
- }
- tmp.add(st);
- }
- ans.add(tmp);
- }
- for (Integer i = 0; i < n; i++) {
- if (!row[i] && !h[curK + i] && !r[curK - i + n]) {
- row[i] = true;
- h[curK + i] = true;
- r[curK - i + n] = true;
- curList.add(i);
- dfs(n, row, h, r, curList, curK + 1, ans);
- curList.remove(i);
- row[i] = false;
- h[curK + i] = false;
- r[curK - i + n] = false;
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2696539.html