NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 28 题

完善程序： （国王放置） 在 $n\times m$ 的棋盘上放置 $k$ 个国王，要求 $k$ 个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第 $(x,y)$ 格，国王的攻击的区域是：$(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1)$，$(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)$。读入三个数 $n,m,k$，输出答案。题目利用回溯法求解。棋盘行标号为 $0\sim n-1$，列标号为 $0\sim m-1$。

#include <iostream>
using namespace std;

int n,m,k,ans;
int hash[5][5];
void work(int x,int y,int tot){
	int i,j;
	if (tot==k){
		ans++;
		return;
	}
	do{
		while (hash[x][y]){
			y++;
			if (y==m){
				x++;
				y=[     ①     ];
			}
			if (x==n)
				return;
		}
		for (i=x-1;i<=x+1;i++)
			if (i>=0&&i<n)
				for (j=y-1;j<=y+1;j++)
					if (j>=0&&j<m)
					   [	        ②         ];
		[        ③         ];
		for (i=x-1;i<=x+1;i++)
			if (i>=0&&i<n)
				for (j=y-1;j<=y+1;j++)
					if (j>=0&&j<m)
					    [	     ④     ];
		y++;
		if (y==m){
			x++;
			y=0;
		}
		if (x==n)
			return;
	}
	while (1);
}
int main(){
	cin >> n >> m >> k;
	ans=0;

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考回溯法在棋盘上的经典应用。拿到题先想：怎么找下一个能放的位置？用do-while循环跳过已攻击区域，找到第一个空位就放，放完递归往下走，回退时记得把标记擦掉。

很多同学在回溯时只记得标记攻击范围，忘记在递归返回后把hash[i][j]减回去，导致同一格被多次覆盖，最后ans数偏小。还有同学没看清y坐标换行时应该重置为0而不是保持m，或者把work(x,y,tot+1)写成了work(x+1,y,tot)，这样会漏掉同一行后续位置。

这道题考查的是回溯法（深度优先搜索）在棋盘放置问题中的应用，核心是：在n×m棋盘上放k个互不攻击的国王，统计方案数。命题人喜欢在这里挖坑，因为攻击范围是8个方向，标记数组hash[i][j]记录的是“被覆盖次数”，而不是“是否可放”，所以回溯时必须把+1和-1配对，否则状态就乱了。

拿到题先想什么？先想怎么找下一个能放的位置。代码里用do-while循环，y从当前值开始往后扫，遇到hash[x][y]>0就跳过，直到找到第一个hash为0的位置。如果扫到y==m，说明这一行用完了，要换行：x++，y重置为0。这里①就是0，因为换行后列标号从头开始，这是最容易看错的细节。

找到空位后，先标记周围8格：②填hash[i][j]++（或++hash[i][j]，本质一样）。然后递归放置下一个国王：③填work(x,y,tot+1)。注意递归参数不变x,y，因为当前格子已经占用了，继续从同一格往后扫，直到扫完这一行或找到新位置。很多同学会误以为要x++，其实不需要，因为循环里已经处理了换行，直接递归即可。

递归返回后必须回退：④填hash[i][j]--（或--hash[i][j]），把刚才标记的取消，这样才能保证同一格被多次尝试时状态正确。最后y++，如果y==m则x++、y=0，继续下一行。整个循环用do-while(1)包住，因为每次都要尝试放一个国王。

主函数里，memset(hash,0,sizeof(hash))清零，然后⑤填work(0,0,0)，从左上角开始尝试放第1个国王（tot初始为0，递归里tot+1就是第2个）。这样就能遍历所有合法放置方案，ans累加。

易错点再强调一遍：回溯时标记和取消标记必须对称；列坐标换行时y=0；递归参数不要乱改。考频趋势看数据：回溯法在题库里只考了9题，覆盖6个级别，2007、2009、2010、2012、2020、2025各1题（2025年有4题，说明近年热度上升）。NOIP普及组初赛每年1题，属于稳定考点。结合2025年回溯法考了4题的势头，未来几年在普及组或GESP五级、六级里继续出现的可能性很大，尤其是结合其他算法（如动态规划、位运算优化）的混合题型。暂无足够依据预测具体年份，但建议复习时重点练回溯+标记数组的经典模型。