1. 题目
2. 读题(需要重点注意的东西)
思路(dfs):
完整思路+斜线与反斜线的推导与[AcWing]AcWing 843. n-皇后问题(C++实现)完全相同,在此不再赘述。
3. 解法
---------------------------------------------------解法---------------------------------------------------:
class Solution {
int N = 20;
// 每行、每列、每条斜线都不能放超过一个皇后
boolean[] col = new boolean[N];
boolean[] dg = new boolean[N];
boolean[] udg = new boolean[N];
String[][] g = new String[N][N];
List<List<String>> list = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
list.clear();
// 图g初始化
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
g[i][j] = ".";
dfs(0,n);// 从第0行开始遍历
return list;
}
public void dfs(int u,int n){
// u为行
// 如果u == n,走到了最后,则输出每一行
if(u == n){
List<String> temp = new ArrayList<>();
for(int i = 0;i < n;i++){
String s = "";
for(int j = 0;j < n;j++){
s += g[i][j];
}
temp.add(s);
}
list.add(temp);
return;
}
// 遍历每一列
for(int i = 0;i < n;i++){
if(!col[i] && !dg[u - i + n] && !udg[u + i]){
col[i] = dg[u - i + n] = udg[u + i] = true;
g[u][i] = "Q";
dfs(u+1,n);
// 恢复现场
col[i] = dg[u - i + n] = udg[u + i] = false;
g[u][i] = ".";
}
}
}
}
可能存在的问题:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
dfs的应用