(国王放置)在 $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 \sim n-1$ ,列标号为 $0 \sim m-1$ 。试补全程序。

#include <cstdio>
#include <cstring>

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 = ___(1)___;
            }
            if (x == n)
                return;
        }
        for (i = x - 1; i <= x + 1; i++)
            if (i >= && i < n)
                for (j = y - 1; j <= y + 1; j++)
                    if (j >= 0 && j < m)
                        ___(2)___;
        ___(3) ;
        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)
                        hash[i][i]--;
        ___(4)___;
        if (y == m) {
            x++;
            y = 0;
        }
        if (x == n)
            return;
    } while (1);
}

int main() {
    scanf("%d%d%d", & n, & m, & k);
    ans = 0;
    memset(hash, 0, sizeof(hash));
    ___(5)___;
    printf("%d\n", ans);
    return 0;
}