| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 72 | 4 | 4 | 7.018% |
Kasandra je napokon otvorila svoju prvu turističku agenciju. Njezina putovanja zasad su ograničena na Hrvatsku, koju možemo zamisliti kao tablicu dimenzija $N \times M$. Neka polja su lijepa i označena su znakovima “.”, dok su druga ružna i označena znakovima “#”. Turisti se mogu kretati samo u četiri osnovna smjera: gore, dolje, lijevo i desno.
Kasandra trenutno ima isplaniranih $Q$ izleta, i za svaki od njih ju zanima minimalan potreban broj koraka od početne točke do završnog odredišta, ne prolazeći pritom ni jednim ružnim poljem. U slučaju da je nemoguće doći od početne točke do odredišta, ispišite $-1$.
U prvom su retku prirodni brojevi $N$ ($1 ≤ N ≤ 300$), $M$ ($1 ≤ M ≤ 300$) i $Q$ ($1 ≤ Q ≤ 100\,000$) iz teksta zadatka.
U sljedećih $N$ redaka nalazi se tablica opisana na način iz teksta zadatka.
U sljedećih $Q$ redaka nalaze se četvorke brojeva $A_i$, $B_i$, $C_i$, $D_i$ ($1 ≤ A_i, C_i ≤ N$) te ($1 ≤ B_i, D_i ≤ M$) gdje par brojeva $(A_i, B_i)$ označava redak i stupac početne točke te $(C_i, D_i)$ označava redak i stupac završnog odredišta.
Potrebno je ispisati Q redaka, u $i$-ti udaljenost početne točke i odredišta $i$-tog izleta.
5 6 4 #...#. ...... #.#.#. ....#. ...... 4 1 4 1 2 4 1 3 5 1 3 2 5 1 4 1
0 2 3 1
4 4 3 .... .... ##.. .#.. 4 1 3 3 2 3 1 1 1 4 4 1
-1 3 -1