犀牛云做的网站好不好,品牌建设什么意思,昌大建设是哪里的,网页视频解析下载目录
棋盘问题
leetcode51题.N皇后 对回溯算法感兴趣的朋友也可以多多支持一下我的其他文章。
回溯算法详解-CSDN博客
经典的回溯算法题leetcode组合问题整理及思路代码详解-CSDN博客
经典的回溯算法题leetcode子集问题思路代码详解-CSDN博客
经典的回溯算法题leetcode全…目录
棋盘问题
leetcode51题.N皇后 对回溯算法感兴趣的朋友也可以多多支持一下我的其他文章。
回溯算法详解-CSDN博客
经典的回溯算法题leetcode组合问题整理及思路代码详解-CSDN博客
经典的回溯算法题leetcode子集问题思路代码详解-CSDN博客
经典的回溯算法题leetcode全排列问题思路代码详解-CSDN博客
棋盘问题
一般棋盘问题都是用回溯算法来做的我们之前说过回溯算法是一种暴力方法尝试每一种可能思路不难但是写起来很容易出错。
leetcode51题.N皇后
51. N 皇后 - 力扣LeetCode 按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的n 皇后问题的解决方案。 每一种解法包含一个不同的n皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2 输入n 1
输出[[Q]] class Solution { //存放结果集的变量resListListString res new ArrayList();public ListListString solveNQueens(int n) {char[][] map new char[n][n];//初始化for(int i 0;i n; i){for(int j 0; j n; j){map[i][j] .;}}backTrack(map, 0, n);return res;}//回溯函数参数有棋盘二维字符类型、处理到了第几行、一共有几行void backTrack(char[][] map, int row, int n){// 结束条件处理到最后一行if(row n){res.add(help(map, n));return;}// 递归回溯for(int col 0; col n; col){// 判断能否存放皇后if(isValid(map, row, col, n)){map[row][col] Q;backTrack(map, row1, n);map[row][col] .;}}}boolean isValid(char[][] map, int row, int col, int n){// 判断列for(int i 0; i row; i){if(map[i][col] Q){return false;}}// 判断右斜for(int i row - 1, j col - 1; i 0 j 0; i--, j--){if(map[i][j] Q){return false;}}// 判断左斜for(int i row - 1, j col 1; i 0 j n; i--, j){if(map[i][j] Q){return false;}}return true;}// 把二位字符数组转为ListStringListString help(char[][] map, int n){ListString temp new ArrayList();for(int i 0; i n; i){StringBuilder build new StringBuilder();for(int j 0; j n; j){build.append(map[i][j]);}temp.add(build.toString());}return temp;}
}
