2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Расстановка коней
Сообщение26.12.2009, 19:49 
Собственно говоря имеется задача:

Найдите количество способов расставить на шахматной доске размером N*N ровно K коней таким образом, чтобы ни один из них не бил другого. Все кони одинаковые, поэтому если в какой-то расстановке поменять местами двух коней, то это будет та же самая расстановка.

Входные данные
В единственной строке находятся два целых числа N (1 <= N <= 6) и K (0 <= K <= N*N).

Выходные данные
Выведите искомое количество способов.

Примеры:

Ввод

Пример 1
2 1

Пример 2
3 2

Вывод

Пример 1
4

Пример 2
28

Сделал задачу с помощью рекурсивного перебора:
Код:
Var
a,c:array[0..20,0..20] of integer;
q,fact,result,j,i,k,n:longint;
dx:array[0..7] of integer=(-2, -1,  1,  2,  2,  1, -1, -2);
dy:array[0..7] of integer=( 1,  2,  2,  1, -1, -2, -2, -1);

procedure move(x,y,d:integer); // функция определяет все клетки, которые бьет конь на координатах x и y
Var i:integer;
begin
for i:=0 to 7 do
if (x+dx[i]>=0) and (x+dx[i]<n) and (y+dy[i]>=0) and (y+dy[i]<n) then
inc(a[x+dx[i],y+dy[i]],d)
end;

procedure solve(size:integer); // сам перебор
var
i,j:longint;
begin
if q=1 then exit;

if size=k then
begin
inc(result);
end
else

begin

for i:=0 to n-1 do
for j:=0 to n-1 do
if (a[i,j]=0) then
begin
a[i,j]:=1;
move(i,j,1);
solve(size+1);
a[i,j]:=0;
move(i,j,-1);
end;

end;

end;

begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n,k);
result:=0;
q:=0;

for i:=0 to n-1 do
for j:=0 to n-1 do begin a[i,j]:=0;c[i,j]:=0; end;

fact:=1;
for i:=1 to k do
fact:=fact*i;

solve(0);

writeln(result div fact);

end.

Так вот, алгоритм работает, однако не укладывается в желаемое время из-за того, что я учитываю "одинаковые" (по условию задачи) расстановки. Хотелось бы узнать способ, который бы позволил разрешить эту проблему.

 
 
 
 Re: Расстановка коней
Сообщение26.12.2009, 20:41 
Во первых, кони на белом поле бьют только чёрные поля, и наоборот.
Я бы решал так:
Разбиваю $K$ разными способами на два числа $K=K_1+K_2, 0 \le K_1 \le N^2, 0 \le K_2 \le N^2$ - количество коней на белых и чёрных полях.
$K_1$ коней можно расставить на белых полях совершенно произвольным способом, максимум - $C^{18}_9=48620$ вариантами. Для каждого варианта считаю все непобитые чёрные поля $N_2$, и если оно не меньше $K_2$, то у нас есть очередные $C^{N_2}_{K_2}$ вариантов расстановки $K$ коней.
Ещё из симметрии можно учитывать только случаи $K_1\le K_2$, умножив при необходимости на два.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group