Misolovac

@Admin: da li mozesh da dash neki hint za ovaj zadatak (posto ga niko josh nije reshio)?

Ja imam ideju, ali onda radi samo na manjim sluchajevima.

Moja ideja je da se za svaku pozociju [x][y] (x je pozicija misa, y je pozicija macke) racuna da li je ona pobednicka za misa kada je on na potezu, i kada je macka na potezu, ali bi to radilo previshe sporo (a i ne bi imao toliko memorije na raspolaganju) za vece primere ...

Pa ideja je da se "puste" 3 BFS-a...

Koliko ja vidim neko ga je resio :)

Poz,
Z

hmm ... josh neki hint? :)

Verovatno cu da lupim :), al aj da pokusam:

Pustimo BFS misa, macke i sira. Sad samo pogledamo da li na neko od susednih polja od sira moze mis brze stici od macke. Ako moze ispisujemo 1, ako ne onda 0.

Slao sam ovo resenje i prolazi prvi, cetvrti i deveti primer, mada je mozda moja greska negde u implementaciji...

Sa m je obelezena macka, sa s je obelezen mis, a sa r je obelezen sir, sa . prazno polje, sa * zid.
....s....
.........
.........
.........
...***...
...***...
.*******.
....r....
.*******.
...***...
...***...
...***...
....m....

Misu do oba (ima samo dva na koja moze da dodje) treba 10 (ako sam dobro izbrojao) poteza, a macki 9 (bitno je da treba vise), ali mis moze da dodje do prvog zida. Ako numerisemo tako da je gornje levo teme (1, 1), onda on dodje do polja (5, 4). Sad kad krene prema siru odatle sigurno jede sir. Ako je macka krenula na levu stranu, on ide na desnu i obrnuto. Ako je macka na jednakom rastojanju od ta dva susedna polja sira, onda ce mis stici pre na koju god stranu da krene jer je polje (5, 4) blize siru nego polje (5, 13). Macka ne moze pre misa da dodje na polje (5, 4)!!!!!

Nadam se da je jasan test primer.

Slobo, radi mi program za tvoj primer :)

ali zato :

Test 1 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 4 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 5 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.13 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 8 Prekoraceno vremensko ogranicenje
Test 9 Prekoraceno vremensko ogranicenje
Test 10 Prekoraceno vremensko ogranicenje

:(

Malo sam prepravio, i trenutno mi samo poslednja dva pucaju na vremenu :)

Test 1 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.08 sekunde
Test 9 Tacno resenje vreme izvrsavanja programa 0.94 sekunde
Test 10 Tacno resenje vreme izvrsavanja programa 0.38 sekunde

Yess :)

Svaka cast ;)