1.【NOIP2009】国王放置
在n*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~n-1，列标号为0~m-1。
#include
<iostream>
#include <cstring>
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）①处应填（ ）
A. 1 B. 0
C. x D. m
（2）②处应填（ ）
A. hash[i][j]++ B. hash[i][j]--
C. hash[i][j]=0 D. hash[i][j]=1
（3）③处应填（ ）
A. work(x, y,
tot++) B. work(x, y, ++tot)
C. work(x, y, tot+1) D. work(x, y, tot)
（4）④处应填（ ）
A. hash[i][j]++ B.
hash[i][j]--
C. hash[i][j]=0 D.
hash[i][j]=1
（5）⑤处应填（ ）
A. work(0, 0, 0)
B.
work(0, 0, 1)
C. work(1, 1, 1) D.
work(n, m, k)