国王放置

在 $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;
	memset(hash,0,sizeof(hash));
	[        ⑤       ] ;
	cout << ans << endl;
	return 0;
}

1. ①处应填（ ）{{ select(1) }}

• 1
• 0
• x
• m

2. ②处应填（ ）{{ select(2) }}

• hash[i][j]++
• hash[i][j]--
• hash[i][j]=0
• hash[i][j]=1

3. ③处应填（ ）{{ select(3) }}

• work(x, y, tot++)
• work(x, y, ++tot)
• work(x, y, tot+1)
• work(x, y, tot)

4. ④处应填（ ）{{ select(4) }}

• hash[i][j]++
• hash[i][j]--
• hash[i][j]=0
• hash[i][j]=1

5. ⑤处应填（ ）{{ select(5) }}

• work(0 , 0 , 0)
• work(0 , 0 , 1)
• work(1 , 1 , 1)
• work(n , m , k)