leetcode 51 N 皇后
原题链接:
https://leetcode.cn/problems/n-queens/
题目描述
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例1:
输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例2:
输入:n = 1
输出:[[“Q”]]
提示:
1 <= n <= 9
解题思路
我们用递归来解决这个问题:
我们一行一行的去验证哪列可以放置皇后,
(因此这个思路就推导出,需要循环加递归)
每到一行,我们只需要验证他前面皇后放的位置,来确定他哪里能放.
验证的方法:
同一列有的肯定不能放了
还有就是斜线位置怎么验证,
举个例子:
A 点(1,2) 和B 点 (2,3) 这两个点在一条斜线上,
那么 1-2 肯定等于 2 - 3 .,
也就是A 的行号 - B 的行号 等于A 的列号 - B 的列号.文章来源:https://www.toymoban.com/news/detail-470143.html
代码演示
/**
* 主函数 leetcode 可以复制进去测试
* @param n
* @return
*/
public static List<List<String>> solveNQueens(int n) {
ArrayList<List<String>> ans = new ArrayList<>();
String[][]que = init(n);
int[] record = new int[n];
process(0,n,record,que,ans);
return ans;
}
/**
*
* @param N
* @param index
* @param record
* @param ans
* @param queens
*/
public static void process(int N ,int index,int[]record,String[][]ans,List<List<String>> queens){
//当考察到N 说明已经全部考察过了.是符合要求的.直接把答案加进去
if (index == N ){
queens.add(convert(ans));
return;
}
// 开始考察当前所到的行,哪一列可以放置
for (int row = 0; row < N;row++){
if(check(record,index,row)){
record[index] = row;
ans[index][row] = "Q";
process(N,index+1,record,ans,queens);
//每次递归后要恢复原状,不然会影响下次判断如何放置Q
ans[index][row] = ".";
}
}
}
/**
* 考察哪一列 可与放置皇后
* @param record
* @param col
* @param row
* @return
*/
public static boolean check(int[]record,int col,int row){
//和之前放置过的皇后去做比较
for (int i = 0; i < col;i++){
if (record[i] == row || Math.abs(record[i] - row) == Math.abs(col - i) ){
return false;
}
}
return true;
}
/**
* 初始化一个二维数组
* @param N
* @return
*/
public static String[][] init(int N){
String[][] ques = new String[N][N];
for (int i = 0; i < N;i++){
for (int j = 0; j < N;j++){
ques[i][j] = ".";
}
}
return ques;
}
/**
*
* @param ques
* @return
*/
public static List<String> convert(String[][]ques){
ArrayList<String> que = new ArrayList<>();
for (String[] ans : ques){
String sb = "";
for (String str : ans){
sb += str;
}
que.add(sb);
}
return que;
}
leetcode52 N 皇后II
Leetcode 52 N 皇后 II文章来源地址https://www.toymoban.com/news/detail-470143.html
到了这里,关于leetcode51. N 皇后 (java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!