网站建设 招聘需求,嘉兴网站建设电话,微网站网站模板建站,wordpress dux添加统计代码题目链接
leetcode在线oj题——N皇后
题目描述
按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
给你一个整数 n #xff…题目链接
leetcode在线oj题——N皇后
题目描述
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
解题思路
使用深度搜索的方法按照先行后列的顺序查看每一个位置是否满足条件
先从第一行第一列开始使这个位置占一个皇后显然第一行和第一列与其所在斜线都无法再放皇后了 然后按照顺序将第二个皇后放在第二行第三列 显然这种放法只能支持三个皇后 那么回退到上一个状态第一个皇后在第一行第一列按照顺序将第二个皇后放在第二行第四列 显然这种放法也是只能放三个那么再次回退到上一个状态按照顺序将第二个皇后放在第三行第二个这时和放在第二行第三列是对称的因此结果一致显然也只能放四个皇后状态回溯到上一个状态
再将第二个皇后放在第三行第四列显然这种情况也是只能最多放三个 其他两个位置也和上面的位置是对称的因此将第一个皇后放在第一行第一列的情况是没有结果的状态回溯到没有放皇后的状态
按照顺序我们将第一个皇后放在第一行第二位 再按照顺序将第二个皇后放在第二行第四列 按照顺序将第三个皇后放在第三行第一列上可以发现这种情况可以放到第四个皇后状态再次回溯到第一个状态第一个皇后放在第一行第二列上 按照顺序将皇后放在第三行第一列可以发现最终产生的结果和上一次的结果一样因此状态再次退回到没有一个皇后的状态
按照顺序将第一个皇后放在第一行第三列上 然后按照顺序将第二个皇后放在第二行第一列上 按照顺序第三个皇后放在第三行第四列上可以发现最终也可以得到最终的结果 事实上把第一个皇后放在第一行第三列上和放在第一行第二列上是对称的情况因此得到的结果也是对称的
而将第一个皇后放在第一行第四列上和放在第一行第一列上是对称的情况因此也得不到最后的结果
按照上面的思想可以写出下面的代码
代码
class Solution {static class Pair{public int x;public int y;public Pair(int x, int y){this.x x;this.y y;}}static void DFS(ListListPair result, ListPair curRet,int curRow, int n){//每一行都有元素当前结果是可行的if(curRow n){result.add(new ArrayList(curRet));return;}//遍历每一列for (int i 0; i n; i) {if(isValidPos(curRet, curRow, i)){curRet.add(new Pair(curRow, i));//处理下一行DFS(result, curRet, curRow 1, n);//回溯curRet.remove(curRet.size() - 1);}}}/*** 判断当前位置是否有效* param curRet* param row* param col* return*/private static boolean isValidPos(ListPair curRet, int row, int col) {//查看每一个已经存储的点与该点是否有冲突for (int i 0; i curRet.size(); i) {Pair pair curRet.get(i);if(pair.y col || pair.x pair.y row col ||pair.x - pair.y row - col){return false;}}return true;}private static ListListString transResult(ListListPair result, int n){ListListString finalResult new ArrayList();for (int i 0; i result.size(); i) {//一种方案ListPair curRet result.get(i);ListStringBuffer stringList new ArrayList();//先将所有位置都设置为.for (int j 0; j n; j) {StringBuffer stringBuffer new StringBuffer();for (int k 0; k n; k) {stringBuffer.append(.);}stringList.add(stringBuffer);}for (int j 0; j curRet.size(); j) {//一种方案中的位置Pair pair curRet.get(j);//再将对应位置设置为QstringList.get(pair.x).setCharAt(pair.y, Q);}//重新创建一个ret存储StringList中StringBuffer.toString后的字符串ListString ret new ArrayList();for (int j 0; j stringList.size(); j) {ret.add(stringList.get(j).toString());}finalResult.add(ret);}return finalResult;}public static ListListString solveNQueens(int n) {ListListPair result new ArrayList();ListPair curRet new ArrayList();DFS(result, curRet, 0, n);return transResult(result, n);}
}
