【Hot 100 刷题计划】 LeetCode 51. N 皇后 | C++ 回溯算法状态数组

LeetCode 51. N 皇后 题目描述题目级别困难按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题 研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题 的解决方案。每一种解法包含一个不同的n皇后问题 的棋子放置方案该方案中Q和.分别代表了皇后和空位。 解法一DFS 逐行放置与绝对值校验这是回溯算法的最经典应用。我们不需要在一个N × N N \times NN×N的格子里一个个盲目去试因为题目明确规定“同行不能有皇后”。因此我们可以按行进行 DFS 递归每一层递归负责在当前行u中找一个合适的列i放置皇后。放置前通过check函数校验是否合法。这里的校验逻辑非常具有几何直觉同一列不冲突j ! y。同一斜线不冲突利用斜率为 1 和 -1 的直线特性如果两个点在同一条斜线上它们的横坐标之差的绝对值必然等于纵坐标之差的绝对值即abs(i - x) ! abs(j - y)。 C 代码实现 (精简修正版)classSolution{public:vectorvectorstringres;vectorstringtmp;vectorvectorstringsolveNQueens(intn){// 优雅初始化生成一个 n 行每行包含 n 个 . 的字符串数组tmpvectorstring(n,string(n,.));// 从第 0 行开始深度优先搜索dfs(0,n);returnres;}voiddfs(intu,intn){// 递归终止条件已经成功放置到了第 n 行0 到 n-1 都放好了if(un){res.push_back(tmp);return;}// 尝试在当前行 u 的每一列 i 放置皇后for(inti0;in;i){if(check(u,i,n)){tmp[u][i]Q;// 处理节点dfs(u1,n);// 向下递归处理下一行tmp[u][i].;// 回溯撤销处理尝试下一列}}}// 校验在 (x, y) 放置皇后是否合法boolcheck(intx,inty,intn){// 只需要检查 x 行之前的行即可因为下面的行还没放皇后for(inti0;ix;i){for(intj0;jn;j){if(tmp[i][j]Q){// 检查列冲突 或 对角线冲突if(jy||abs(i-x)abs(j-y))returnfalse;}}}returntrue;}}; 解法二状态数组降维打击在基础版本中每次放置皇后都要回头遍历棋盘检查冲突校验的时间复杂度是O ( N 2 ) O(N^2)O(N2)。为了追求极致性能我们可以开辟三个布尔数组专门记录哪些列、哪些斜线已经被占用了col数组记录哪一列有皇后。col[i] true表示第i列被占。dg数组正对角线观察棋盘发现处于同一条正对角线右上到左下,/上的点它们的行号和列号之和是固定的x y const。我们用dg[u i]来标记这条斜线。udg数组反对角线处于同一条反对角线左上到右下,\上的点它们的行号和列号之差是固定的y - x const。为了防止数组下标出现负数我们加上一个偏移量n即用udg[n - u i]来标记这条斜线。有了这三个数组判断一个点能不能放皇后只需要查三个布尔值即可瞬间降维到O ( 1 ) O(1)O(1) C 代码实现 (极客优化版)classSolution{private:vectorvectorstringres;vectorstringboard;// 状态数组因为是对角线最大数量是 2N-1所以开大一点 20 足够应付 n9boolcol[20],dg[20],udg[20];voiddfs(intu,intn){// 成功放置到最后一行收集结果if(un){res.push_back(board);return;}// 尝试在第 u 行的每一列 i 放置皇后for(inti0;in;i){// O(1) 极速校验该列、该正对角线、该反对角线均没有被占用if(!col[i]!dg[ui]!udg[n-ui]){board[u][i]Q;// 同步更新三个状态数组宣告占领col[i]dg[ui]udg[n-ui]true;dfs(u1,n);// 向下递归// 回溯撤销皇后并释放三个状态数组的占领col[i]dg[ui]udg[n-ui]false;board[u][i].;}}}public:vectorvectorstringsolveNQueens(intn){board.assign(n,string(n,.));// 初始化状态数组memset(col,false,sizeofcol);memset(dg,false,sizeofdg);memset(udg,false,sizeofudg);dfs(0,n);returnres;}};