当前位置：首页 > news >正文

3月7日（130-132题）

news 2026/3/27 5:42:00

130 .2n皇后问题

题目描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法？

n小于等于8。

说明：同一条对角线是指包括两条主对角线的所有对角线，n=5时的棋盘从左上往右下有9条对角线，从右上往左下也有9条对角线。

比如，棋盘为：

1 1 1 1

1 1 1 1
1 1 1 1
1 1 1 1

表示一个4*4的棋盘，所有位置都可放皇后。

则可知有2种放法。

代码

#include<iostream>#include<vector>usingnamespacestd;intn;intboard[10][10];intans=0;// 分别记录黑白皇后在列、主对角线(左上到右下)、副对角线(右上到左下)的占用情况boolb_col[10],b_d1[20],b_d2[20];boolw_col[10],w_d1[20],w_d2[20];voiddfs_white(intr){if(r==n){ans++;// 白皇后也成功放完了，找到一种合法方案return;}for(intc=0;c<n;++c){// 白皇后放置条件：必须是1，且没有受到其他白皇后的攻击if(board[r][c]==1&&!w_col[c]&&!w_d1[r+c]&&!w_d2[r-c+n]){w_col[c]=w_d1[r+c]=w_d2[r-c+n]=true;dfs_white(r+1);// 递归放下一行w_col[c]=w_d1[r+c]=w_d2[r-c+n]=false;// 回溯}}}voiddfs_black(intr){if(r==n){dfs_white(0);// 黑皇后8行全放完了，开始放白皇后return;}for(intc=0;c<n;++c){// 黑皇后放置条件：必须是1，且没有受到其他黑皇后的攻击if(board[r][c]==1&&!b_col[c]&&!b_d1[r+c]&&!b_d2[r-c+n]){board[r][c]=2;// 标记黑皇后已经占据该位置，白皇后不能再放b_col[c]=b_d1[r+c]=b_d2[r-c+n]=true;dfs_black(r+1);// 递归放下一行// 回溯恢复状态b_col[c]=b_d1[r+c]=b_d2[r-c+n]=false;board[r][c]=1;}}}intmain(){if(cin>>n){for(inti=0;i<n;++i){for(intj=0;j<n;++j){cin>>board[i][j];}}dfs_black(0);// 从第0行开始放黑皇后cout<<ans<<endl;}return0;}

总结

先利用 DFS 放nnn个黑皇后，并在棋盘上标记它们占据的位置。

黑皇后放完后，再利用另一个 DFS 在剩下的空位放nnn个白皇后。

只需要分别用三个数组（列、主对角线、副对角线）来判断黑白皇后的攻击范围即可

131.8皇后·改

规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。

代码

#include<iostream>#include<algorithm>usingnamespacestd;intboard[8][8];intmax_sum=0;// 记录列、主对角线、副对角线boolcol[8],d1[16],d2[16];voiddfs(intr,intcurrent_sum){if(r==8){// 8个皇后都放好了，比较并更新最大和max_sum=max(max_sum,current_sum);return;}for(intc=0;c<8;++c){if(!col[c]&&!d1[r+c]&&!d2[r-c+8]){// 标记占用col[c]=d1[r+c]=d2[r-c+8]=true;// 递归进入下一行，并累加当前格子的数字dfs(r+1,current_sum+board[r][c]);// 回溯col[c]=d1[r+c]=d2[r-c+8]=false;}}}intmain(){for(inti=0;i<8;++i){for(intj=0;j<8;++j){cin>>board[i][j];}}dfs(0,0);// 从第0行开始，初始和为0cout<<max_sum<<endl;return0;}

总结

最基础的 8 皇后问题，只是在找到有效方案时，多了一步求和的操作。需要在 DFS 参数中带上当前已经累计的分数，当到达第 8 行（找到一个可行解）时，更新全局最大值即可。

132.棋盘多项式

题目描述

八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张n*n的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。

此题，给你棋盘的规模n，以及挖洞情况，求放k个车的方案数(k从0到最多可放车数)

代码

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intn;intboard[10][10];boolhas_rook[10][10];longlongans[100];// ans[k] 记录放k个车的方案数intmax_k=0;// 记录最多能放多少个车// 检查当前位置能否放车boolcan_place(intr,intc){// 向上检查：遇到洞(0)就停止，遇到车说明冲突for(inti=r-1;i>=0;--i){if(board[i][c]==0)break;if(has_rook[i][c])returnfalse;}// 向左检查：遇到洞(0)就停止，遇到车说明冲突// (因为我们是从前往后遍历的，所以只需要检查上方和左方)for(intj=c-1;j>=0;--j){if(board[r][j]==0)break;if(has_rook[r][j])returnfalse;}returntrue;}// u 表示当前枚举到的一维位置索引(0 到 n*n-1)，k 表示当前已经放了几个车voiddfs(intu,intk){if(k>0){max_k=max(max_k,k);// 记录出现过的最大车数}// 尝试在 u 及其之后的位置放下一个车for(inti=u;i<n*n;++i){intr=i/n;intc=i%n;if(board[r][c]==1&&can_place(r,c)){has_rook[r][c]=true;ans[k+1]++;// 成功放下了第 k+1 个车，方案数累加dfs(i+1,k+1);// 探索下一个位置has_rook[r][c]=false;// 回溯}}}intmain(){if(cin>>n){for(inti=0;i<n;++i){for(intj=0;j<n;++j){cin>>board[i][j];}}dfs(0,0);// 从第0个位置开始，当前放了0个车// 按题目示例输出，有几行说明最大能放几个车for(inti=1;i<=max_k;++i){cout<<ans[i]<<endl;}}return0;}