| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Uprava grada Zagreba odlučila je sagraditi novo parkiralište. Za to će iskoristiti zemljište pravokutnog oblika koje možemo zamisliti kao matricu s N redaka i M stupaca. Kako bi privukao goste i time povećao prihod, gradonačelnik je na unaprijed određena polja zemljišta odlučio postaviti vodoskoke, zdence, česme i druge vrste fontana. Preostala polja predviđena su za kretanje vozila, a preuredit će se prema jednoj od dviju mogućnosti:
Vozila se mogu kretati po parkiralištu tako da se u svakom koraku pomaknu na susjedno polje u jednom od četiriju smjerova (sjever, jug, istok ili zapad), a parkiralište mora biti sagrađeno tako da se u svakom trenutku sa svakog parkirnog mjesta može doći do ulaza/izlaza u parkiralište koje se nalazi u gornjem-lijevom polju (na presjeku prvog retka i prvog stupca), tj. da vozila koja stoje na parkirnim mjestima ne blokiraju izlaz drugim vozilima. Drugim riječima, svako parkirano vozilo mora biti u stanju izaći s parkirališta bez pomicanja drugih parkiranih vozila.
Pomozite gradonačelniku i odredite najveći mogući broj parkirnih mjesta za zadano zemljište.
Napomena: Polje u prvom retku i prvom stupcu je ulaz u parkiralište i nije namijenjeno za parkiranje te će uvijek biti slobodno.
U prvom su retku prirodni brojevi N i M (1 ≤ N ≤ 6, 1 ≤ M ≤ 100), broj redaka i stupaca zemljišta.
Sljedećih N redaka sadrži po M znakova koji opisuju izgled zemljišta:
U jedini redak ispišite traženi maksimalni mogući broj parkirnih mjesta.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | N, M ≤ 4 |
| 2 | 10 | N = 2 |
| 3 | 20 | N = 3 |
| 4 | 20 | N = 4 |
| 5 | 20 | N = 5 |
| 6 | 20 | N = 6 |
3 3 ... .x. ...
2
3 3 ... ..x ...
4
3 6 .x..x. ..x.x. ......
3
4 5 ....x ....x ..x.. .x..x
7
Pojašnjenje četvrtog primjera: jedan mogući raspored parkirnih mjesta:
.PPPx ....x .Px.P PxP.x