Pripreme za algoritme(5)

Danas ćemo malo proučiti zadatak, Klingonci koji se pojavio na Žup. 2012, srednje škole. Sada da ne kopiram tekst zadatka u cijelosti samo ću vam reći bitne stvari. Unosimo A,B i C. Cilj je razmjestiti što više klingonaca u matrici A*B na razmaku od C.
Ulaz:

5 5 2
Izlaz:
6

Desno vidimo pokazanu matricu 5*5 i smještenih 6 klingonaca. Naravno ovo je samo jedan od mogućih prikaza matrice.
  Zamislimo to kao jednu situaciju u životu, kao na primjer tramvaj. Kada uvijek uđemo u tramvaj stanemo u kut, nikada u centar jer želimo zauzeti što manje prostora. Ok to nam je prva ideja, poslagati ćemo klingonce po rubovima matrice da zauzmu što manje prostora. Kako smo provjerili sve rubove onda idemo u slijedeći prsten, točnije novi  krug oko matrice samo manji.
 E sad kako ćemo znati je li neki prostor zauzet. Kada postavimo prvog klingonca oko njega zauzmemo prostor algoritmom BFS. I tako samo gledamo kada nađemo prazan prostor stavimo klingonca i zauzmemo njegov prostor.

1.    Pretraživanje po prstenovima, rubovima ili ukrug
2.    Kada  nađemo prazan prostor, broj klingonaca se povečava i oko njega zauzimamo prostor, ne mora nužno to biti sa BFS-om, ali bi bilo lakše
3. Na kraju kada dođemo do središnjeg polja, pretraživanje je gotovo i ispisujemo broj klingonaca