（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;
}

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

• 1
• 0
• x
• m

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

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

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

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

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

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

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

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