网站建设帮助中心,游戏制作软件免费版,会员网站模板,你买域名我送网站一、题目
按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
给你一个整数 n #xff0c;返回所有不同的 n 皇后问题 的解决方案…一、题目
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 来源力扣LeetCode 链接https://leetcode.cn/problems/n-queens/description/
二、C解法
我的思路及代码
采用回溯的思想。这里需要一个判断的函数 isValid 来处理当前位置是否是可选的位置。每一次选择的时候都会前进一行然后在当前行中选择可用的列。如果这个列是可用的那么就可以选择此路径然后继续后面的回溯如果不可用则继续往下找。本质是一个全排列的问题。由于我们的方式是从一行一行的往下找那么在 isValid 中就不必判定左下角和右下角的合理情况这必然是可选的。
class Solution {
public:vectorvectorstring ans;bool isValid(int row,int col,vectorstring temp){int rowTemp row;int colTemp col;//判断列有没有棋子for(int i0;itemp.size();i){if(temp[i][col] Q)return false;}//判断左上有没有棋子for(;rowTemp0colTemp0;rowTemp--,colTemp--){if(temp[rowTemp][colTemp] Q)return false;}//判断右上有没有棋子for(rowTemp row,colTemp col;rowTemp0colTemptemp.size();rowTemp--,colTemp){if(temp[rowTemp][colTemp] Q)return false;}return true;}void backtrance(vectorstring temp,int row){if(rowtemp.size()){ans.push_back(temp);return;}for(int col0;coltemp.size();col){if(isValid(row,col,temp)){temp[row][col] Q;backtrance(temp,row1);temp[row][col] .;}}}vectorvectorstring solveNQueens(int n) {vectorstring temp(n,string(n,.));backtrance(temp,0);return ans;}
};时间复杂度O(N!)其中 N 是皇后数量空间复杂度O(N)其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合递归调用层数不会超过 N数组的长度为 N每个集合的元素个数都不会超过 N
官方参考代码
方法一基于集合的回溯
采用了集合的方式来存储各个线上皇后的情况本质还是回溯算法。
class Solution {
public:vectorvectorstring solveNQueens(int n) {auto solutions vectorvectorstring();auto queens vectorint(n, -1);auto columns unordered_setint();auto diagonals1 unordered_setint();auto diagonals2 unordered_setint();backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);return solutions;}void backtrack(vectorvectorstring solutions, vectorint queens, int n, int row, unordered_setint columns, unordered_setint diagonals1, unordered_setint diagonals2) {if (row n) {vectorstring board generateBoard(queens, n);solutions.push_back(board);} else {for (int i 0; i n; i) {if (columns.find(i) ! columns.end()) {continue;}int diagonal1 row - i;if (diagonals1.find(diagonal1) ! diagonals1.end()) {continue;}int diagonal2 row i;if (diagonals2.find(diagonal2) ! diagonals2.end()) {continue;}queens[row] i;columns.insert(i);diagonals1.insert(diagonal1);diagonals2.insert(diagonal2);backtrack(solutions, queens, n, row 1, columns, diagonals1, diagonals2);queens[row] -1;columns.erase(i);diagonals1.erase(diagonal1);diagonals2.erase(diagonal2);}}}vectorstring generateBoard(vectorint queens, int n) {auto board vectorstring();for (int i 0; i n; i) {string row string(n, .);row[queens[i]] Q;board.push_back(row);}return board;}
};时间复杂度O(N!)其中 N 是皇后数量空间复杂度O(N)其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合递归调用层数不会超过 N数组的长度为 N每个集合的元素个数都不会超过 N
