Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/lib/plugins/importoldindex/action.php on line 0

Deprecated: Function split() is deprecated in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/inc/auth.php on line 154

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/inc/auth.php on line 456

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/inc/auth.php on line 456

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/inc/auth.php on line 453

Strict Standards: Only variables should be passed by reference in /DISK2/WWW/pavel-rimsky.cz/vyuka/wiki/doku.php on line 71
==== Zadání ====


Na prvním řádku standardního vstupu se nachází číslo M, na druhém řádku číslo N. Najděte nejmenší k takové, že lze na šachovnici o rozměrech MxN rozmístit k dam tak, aby ovládly celou šachovnici, a vypište všechna taková rozmístění k dam.
Formát výstupu:

Každé rozmístění musí být na samostatném řádku. Na každém řádku se musí vyskytovat mezerou oddělená posloupnost pozic. Pozice je dvojice celých čísel oddělených dvojtečkou, které značí po řadě řádek a sloupec šachovnice (řádky a sloupce číslujeme od nuly).
Příklad:
Na vstupu je

  4
  4


Na výstup musíme vypsat:

  0:0 2:2 
  0:1 3:1 
  0:2 3:2 
  0:3 2:1 
  1:0 1:3 
  1:1 1:2 
  1:1 2:1 
  1:1 3:3 
  1:2 2:2 
  1:2 3:0 
  2:0 2:3 
  2:1 2:2 


==== Řešení ====

<code pascal>

{Princip: hledame nejmensi p takove, pro ktere p vhodne rozmistenych dam ovladne celou sachovnici.
 Pro dane p a danou sachovnici m*n hledame vsechny p-prvkove kombinace jejich policek (tedy p-prvkove
 podmnoziny mnoziny jejich policek). Pro kazdou takovou kombinaci overime, jestli by damy rozmistene
 na techto p policek ovladly sachovnici. Pokud jo, vypiseme toto rozmisteni.

 Pred tim, nez zacnete studovat algoritmus, doporucuji, abyste se seznamili s algoritmem pro generovani
 vsech kombinaci (take zverejnen tu na wiki).

 }

{maximalni rozmery sachovnice}
const
  MAX = 16;

{reprezentuje sachovnici}
type
  Sachovnice = record

    {pozice s cislem 0: leve horni policko,
     pozice s cilem 1: policko v prvnim radku a druhem sloupci,
     pozice s cilem 2: policko v prvnim radku a tretim sloupci,...
     pozice s cislem MAX * MAX - 1: prave dolni policko}
    obsazeniPozic: set of 0..(MAX * MAX - 1);

    {rozmery sachovnice}
    m: 0..MAX - 1;
    n: 0..MAX - 1;
  end;

{jakmile algoritmus najde takove p, ze n dam je schopno ovladnout sachovnici, nastavi se tato promenna na "true"}
var
  nalezeno: boolean;

{vraci true, prave kdyz sachovnice "s" je ovladnuta na ni rozmistenymi damami}
function ovladnuto(var s: Sachovnice): boolean;
var
  ovladnuteRadky: set of 0..MAX - 1;
  ovladnuteSloupce: set of 0..MAX - 1;
  ovladnuteHlavni: set of 0..(2 * MAX - 2);    {ovladnute hlavni diagonaly}
  ovladnuteVedlejsi: set of 0..(2 * MAX - 2);  {ovladnute vedlejsi diagonaly}
  i, j, k: integer;
begin
  ovladnuteRadky := [];
  ovladnuteSloupce := [];
  ovladnuteHlavni := [];
  ovladnuteVedlejsi := [];

  {pro kazdou damu na sachovnici zjistime, ktere radky/sloupce/hlavni diagonaly/vedlejsi diagonaly jsou ji ovladnuty}
  for k := 0 to s.m * s.n - 1 do begin
    if k in s.obsazeniPozic then begin
      i := k div s.n;
      j := k mod s.n;
      ovladnuteRadky := ovladnuteRadky + [i];
      ovladnuteSloupce := ovladnuteSloupce + [j];
      ovladnuteHlavni := ovladnuteHlavni + [i - j + s.n - 1];      
      ovladnuteVedlejsi := ovladnuteVedlejsi + [i + j];
    end;
  end;

  {a nakonec zjistime, zda se na sachovnici nahodou nenachazi policko, ktere neni vubec ovladnuto}
  for i := 0 to s.m - 1 do begin
    for j := 0 to s.n - 1 do begin
      if
	  (not (i in ovladnuteRadky))
	  and (not (j in ovladnuteSloupce))
	  and (not ((i - j + s.n - 1) in ovladnuteHlavni))
	  and (not ((i + j) in ovladnuteVedlejsi)) then begin
	    ovladnuto := false;
	    exit;
	  end;
    end;
  end;

  ovladnuto := true;
end;

{vytvori prazdnou sachovnici}
function vytvor(m, n: integer): Sachovnice;
var
  vysledek: Sachovnice;
begin
  vysledek.m := m;
  vysledek.n := n;
  vysledek.obsazeniPozic := [];
  vytvor := vysledek;
end;

{Vytiskne pozice vsech dam na sachovnici. Jestlize sachovnice neni damamy ovladnuta, nevypisuje nic.}
procedure vytiskni(var s: Sachovnice);
var
  i, j: 0..MAX;
begin
  if not ovladnuto(s) then exit;
  nalezeno := true;
  for i := 0 to s.m * s.n - 1 do begin
    if i in s.obsazeniPozic then begin
      write((i div s.n), ':', i mod s.n, ' ');
    end;
  end;
  writeln;
end;

{Vypise vsechna mozna rozmisteni "kolikDam" dam na sachovnici "s" (na ktere uz nejake damy by mohou),
 pricemz prvni novou damu umisti na pozici s cislem "pocinaje". Tato procedura v podstate rekurzivne
 hleda vsechny p-prvkove podmnoziny mnoziny vsech policek, kde p = "kolikDam".}
procedure vypisVse(var s: Sachovnice; kolikDam: integer; pocinaje: integer);
var
  i: integer;
begin
  if (kolikDam = 0) then begin
    vytiskni(s);
  end else if pocinaje = s.m * s.n - kolikDam then begin
    for i := pocinaje to s.m * s.n - 1 do begin
      s.obsazeniPozic := s.obsazeniPozic + [i];
    end;
    vytiskni(s);
    for i := pocinaje to s.m * s.n - 1 do begin
      s.obsazeniPozic := s.obsazeniPozic - [i];
    end;
  end else begin
    s.obsazeniPozic := s.obsazeniPozic + [pocinaje];
    vypisVse(s, kolikDam - 1, pocinaje + 1);
    s.obsazeniPozic := s.obsazeniPozic - [pocinaje];
    vypisVse(s, kolikDam, pocinaje + 1);
  end;
end;

var
  s: Sachovnice;
  pocet: integer;
  m, n: integer;
begin
  readln(m);
  readln(n);
  nalezeno := false;
  pocet := 0;
  s := vytvor(m, n);
  while not nalezeno do begin
    inc(pocet);
    vypisVse(s, pocet, 0);
  end;
end.

</code>