网站设计与网页制作代码大全,一元云购网站怎么做,可以做旅行计划的网站,活动页面设计模板目录题目思考AC代码题目
n 皇后问题研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
思考
首先以N4为例#xff0c;画出解空间树的一部分#xff1a;
根据模板#xff1a;
void backtracking(参数)
{if(终止条件){存放结果… 目录题目思考AC代码 题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
思考
首先以N4为例画出解空间树的一部分
根据模板
void backtracking(参数)
{if(终止条件){存放结果;return;}for(选择本层集合中元素(树中结点孩子的数量就是集合的大小)){处理结点;backtracking(路径,选择列表); //递归回溯撤销处理结果;}
}1、确定回溯函数参数,返回值 当前所在的行(层)当前的棋盘布局。 N的大小
void backtracking(int hang,vectorstring chessboard,int n)全局变量vectorvectorresult; result是个存放chessboard的变量。 这里的chessboard就相当于之前回溯题目中的path、子结果。 2、确定终止条件 当遍历到N的最后一层(n-1)时再往下一层我们就需要返回了。
if(hang n)
{result.push_back(chessboard);return ;
}3、确定单层逻辑 如果本行的某列放入皇后且不违反规则即可进入下一行探索 for(int lie 0;lie n ;lie)
{if(juge_if_valid(hang,lie,chessboard,n) true){chessboard[hang][lie] Q; //放置皇后backtracking(hang1,chessboard,n);chessboard[hang][lie] .; //回溯撤销}}4、判断是否满足分布条件有三个 1、皇后不在同一行 2、皇后不在同一列 3、皇后不在同一斜线上 a、同时我们注意我们探索的时候就是按照深度探索的所以保证了每一行只有一次赋值Q。所以第一个条件不需要特别处理。 b、由于按照深度往下搜索所以判断皇后在同一列的时候可以剪枝
//检查本行之上的行的同一列是否存在Q
for(int i0;ihang;i)
{if(chessboard[i][lie] Q) return false;
}c、由于按照深度往下探索所以判断皇后在同一斜线的时候可以剪枝(注意斜线分为向右上斜和左上斜两个方向)
//检查本行之上的行的右斜线上是否有皇后
for(int ihang-1,jlie-1;i0 j0;i--,j--)
{if(chessboard[i][j] Q) return false;
}
//检查本行之上的行的左斜线上是否有皇后
for(int ihang-1,jlie1;i0 jn;i--,j)
{if(chessboard[i][j] Q) return false;
}AC代码
class Solution {
public:vectorvectorstringresult;bool juge_if_valid(int hang,int lie,vectorstringchessboard,int n){//检查本行之上的行的同一列是否存在Qfor(int i0;ihang;i){if(chessboard[i][lie] Q) return false;}//检查本行之上的行的右斜线上是否有皇后for(int ihang-1,jlie-1;i0 j0;i--,j--){if(chessboard[i][j] Q) return false;}//检查本行之上的行的左斜线上是否有皇后for(int ihang-1,jlie1;i0 jn;i--,j){if(chessboard[i][j] Q) return false;}return true;} void backtracking(int hang,vectorstring chessboard,int n){if(hang n){result.push_back(chessboard);return ;}for(int lie 0;lie n ;lie){if(juge_if_valid(hang,lie,chessboard,n) true){chessboard[hang][lie] Q; //放置皇后backtracking(hang1,chessboard,n);chessboard[hang][lie] .; //回溯撤销}}return ;}vectorvectorstring solveNQueens(int n) {result.clear();//填充初始棋盘vectorstring chessboard(n,string(n,.));backtracking(0,chessboard,n);return result;}
};
