Teoria Obliczeń i Złożoności Obliczeniowej

Cel zadania

Saper to znana gra logiczna polegająca na odkrywaniu pól na planszy stanowiącej pole minowe. W przypadku odkrycia pola zawierającego minę użytkownik przegrywa, w przypadku odkrycia pola bez miny podawana jest informacja o ilości min z nim sąsiadujących.

Zadanie stojące przed Państwem jest nieco odmienne. Na planszy ujawniona jest zawartość niektórych z pól, a celem gry jest takie ustawienie min na planszy, aby zawartość ujawnionych pól była poprawna. Ilość min do rozstawienia może być dowolna lub też dana z góry.

Celem projektu jest napisanie programu, który:

• wczyta opis planszy ze standardowego wejścia,
• znajdzie żądane ustawienie min,
• wypisze rozwiązanie na standardowe wyjście.

Reguły gry

Każde z pól może zawierać minę bądź informację, ile min z nim sąsiaduje. Miny można rozstawić dowolnie, tak jednak, aby ich rozmieszczenie było zgodne z wartością ujawnionych pól. Jeśli ilość min jest określona, plansza wynikowa powinna zawierać dokładnie taką ilość rozstawionych min. W przeciwnym przypadku ilość min do rozstawienia jest dowolna.

Opis wejścia/wyjścia

Program wczytuje opis wejścia ze standardowego wejścia. Pierwszy wiersz składa się z trzech liczb całkowitych. Pierwsza określa szerokość, druga wysokość, a trzecia ilość min na planszy, przy czym wartość 0 oznacza dowolną ilość min. Kolejne wiersze (o jednakowej długości) zawierają kolejne pola planszy - jeden znak odpowiada jednemu polu w następujący sposób:

• * (gwiazdka) - mina,
• 0-8 - pola sąsiadujące z odpowiednią ilością min,
• . (kropka) - pole zakryte.

Wyjściem programu powinna być plansza zawierająca kropki w polach pustych i gwiazdki w polach zawierających miny. Wyjście nie zawiera linii z opisem rozmiarów planszy i ilości min. W przypadku, gdy dla planszy wejściowej nie istnieje rozwiązanie, na wyjściu powinien pojawić się pojedynczy wiersz ze znakiem 0 (zero).

Przykład

Przykładowa plansza gry:

  5 5 3
  .....
  1..2.
  .*...
  ....0
  .....
  

  .....
  ..*.*
  .*...
  .....
  .....
  

Życzymy powodzenia!