dominance_dam [Programování]

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í

 
{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.