做外国美食的视频网站,软文广告经典案例300大全,珠海定制网站建设推广,搜索引擎优化的主题1. 题目
n 皇后问题研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。
给定一个整数 n#xff0c;返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案…1. 题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。
给定一个整数 n返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
输入: 4
输出: [[.Q.., // 解法 1...Q,Q...,..Q.],[..Q., // 解法 2Q...,...Q,.Q..]
]
解释: 4 皇后问题存在两个不同的解法。LeetCode 52题类似要求的是方案数不用枚举出来。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
可参考回溯算法Backtracking Algorithm之八皇后问题
class Solution {vectorvectorstring ans;int N;
public:vectorvectorstring solveNQueens(int n) {vectorstring map(n,string(n,.));N n;dfs(map,0);return ans;}void dfs(vectorstring map, int x){if(x N){ans.push_back(map);return;}for(int i 0; i N; i){if(isok(map,x,i)){map[x][i]Q;dfs(map,x1);map[x][i].;}}}bool isok(vectorstring map, int i, int j){int delta 1;while(i-1 0){if(map[i-1][j]Q)//竖直方向return false;if(j-delta0 map[i-1][j-delta]Q)return false;//左45度if(jdeltaN map[i-1][jdelta]Q)return false;//右45度i--;//向上查找delta;//45度增量}return true;}
};class Solution {int sum 0;
public:int totalNQueens(int n) {vectorstring map(n,string(n,.));for(int i 0; i n; i){map[0][i]Q;dfs(map,0,i,n);map[0][i].;}return sum;}bool isok(vectorstring map, int x, int y, int n){int i 1, j y;while(x 1)//向上遍历看冲突不{if(map[x-1][j]Q)//竖直方向return false;if(j-i0 map[x-1][j-i]Q)//左45度return false;if(jin map[x-1][ji]Q)//右45度return false;i;//45度张角x--;//往上找}return true;}void dfs(vectorstring map, int x, int y, int n){if(xn-1)sum;for(int i 0; i n; i){ //x1下一行if(x1 n isok(map,x1,i,n)){map[x1][i] Q;dfs(map, x1, i, n);map[x1][i] .;}}}
};
