Državno natjecanje 2012. / Osnovna škola (8. razred) - 3. zadatak

Hitori je japanska mozgolomka koju možemo pronaći u mnogim dnevnim novinama.

U ovoj igri za jednog igrača, zadana je NxN ploča u čijem je svakom polju upisana jedna znamenka.

Igrač treba obrisati neke znamenke s ploče tako da vrijedi:

1. Ne smiju se brisati znamenke u susjednim poljima. Susjedna polja su ona koja dijele zajednički brid na ploči (dakle, lijevo, desno, gore, dolje, ali ne ukoso).

2. Nakon brisanja, u svakom retku ploče moraju biti sve preostale znamenke međusobno različite. Također, u svakom stupcu ploče sve neobrisane znamenke moraju biti različite.

3. Broj obrisanih znamenki mora biti što je moguće manji.

U ovom zadatku trebate napisati program koji rješava igru Hitori za zadanu ploču.

ULAZNI PODATCI

prirodan broj N ( 2 ≤ N ≤ 6), dimenzija ploče;

prikaz ploče: N redaka, u svakom po N znamenki odvojenih s po jednim razmakom.

Test podaci će imati sljedeća dodatna ograničenja:

u 30% test-podatka se rješenje dobije brisanjem 3 ili manje znamenki.

u tim i u dodatnih 30% test podataka se rješenje dobije brisanjem jedne ili nijedne znamenke u svakom stupcu.

IZLAZNI PODATCI

potrebno je ispisati ploču nakon brisanja znamenki.

Umjesto svake obrisane znamenke treba ispisati znak *(zvjezdica). Test podaci će biti takvi da se traženo brisanje može napraviti.

PRIMJERI TEST PODATAKA

Ulaz

5
2 4 2 3 1
8 4 0 2 4
2 9 4 1 5
1 3 8 9 3
7 4 6 2 8

Izlaz

* 4 2 3 1
8 * 0 * 4
2 9 4 1 5
1 3 8 9 *
7 * 6 2 8

Objašnjenje

Nakon brisanja 5 znamenki označenih zvjezdicom, u svakom retku i stupcu su svi brojevi različiti.

Ovo je jedno moguće rješenje.

Postoji još jedan način na kojeg možemo riješiti zadatak pomoću 5 brisanja, ali ga ne možemo riješiti pomoću 4 ili manje brisanja.

Ulaz

4
3 4 1 5
3 5 2 9
1 5 9 3
8 6 1 7

Izlaz

3 4 1 5
* 5 2 9
1 * 9 3
8 6 * 7

Objašnjenje

Dovoljna su samo 3 brisanja. Postoji još 5 načina za rješavanje zadatka pomoću 3 brisanja.