(国王放置) 在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。
var
n, m, k, ans: integer;
hash: array[0..4, 0..4] of integer;
procedure work(x, y, tot: integer);
var
i, j: integer;
begin
if tot = k then
begin
inc(ans);
exit;
end;
repeat
while hash[x, y] <> 0 do
begin
inc(y);
if y = m then
begin
inc(x);
y := 1 ;
end;
if x = n then
exit;
end;
for i := x - 1 to x + 1 do
if (i >= 0) and (i < n) then
for j := y - 1 to y + 1 do
if (j >= 0) and (j < m) then
2 ;
3 ;
for i := x - 1 to x + 1 do
if (i >= 0) and (i < n) then
for j := y - 1 to y + 1 do
if (j >= 0) and (j < m) then
4 ;
inc(y);
if y = m then
begin
inc(x);
y := 0;
end;
if x = n then
exit;
until false;
end;
begin
read(n, m, k);
ans := 0;
fillchar(hash, sizeof(hash), 0);
5 ;
writeln(ans);
end.