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

Ivan je za rođendan dobio novu igru koja sadrži igraću ploču, figuricu i upute. Igraću ploču možemo prikazati tablicom znakova koja ima N redaka i M stupaca.

Postoje dvije vrste znakova: '.' i 'X'. Pozicija gornjeg lijevog kuta ploče je (1,1), a donjeg desnog (N,M).

Figurica se može kretati na K načina prema unaprijed zadanim uputama.

Svaki način je opisan u obliku: 'A B' gdje je A broj redova, a B broj stupaca za koje se figurica pomiče.

S pozicije (X,Y) figurica dolazi na poziciju (X+A, Y+B).

Cilj igre je za odreñenu početnu poziciju figurice naći minimalan broj poteza potreban da figurica završi ili na polju sa znakom 'X' ili da izañe izvan tablice.

Ivan je odabrao P početnih pozicija figurice i za svaku izračunao traženi broj poteza.

Pozicije je zapisivao u obliku: 'R S' gdje je R broj retka, a S broj stupca početne pozicije (R, S).

Napišite program koji će odrediti traženi minimalan broj poteza za svaku od P početnih pozicija koje je Ivan odabrao.

ULAZNI PODATCI

U prvom retku nalaze se dva prirodna broja N, M (1 ≤ N, M ≤ 200), dimenzije tablice.

U sljedećih N redaka nalazi se po M znakova, izgled ploče.

U sljedećem retku nalazi se prirodan broj K (1 ≤ K ≤ 20), broj načina kretanja figurice.

U sljedećih K redaka nalaze se dva cijela broja A, B (-200 ≤ A, B ≤ 200), opisi kretanja.

U sljedećem retku nalazi se prirodan broj P (1 ≤ P ≤ 40000), broj početnih pozicija figurice.

U sljedećih P redova nalaze se po dva prirodna broja R, S (1 ≤ R ≤ N, 1 ≤ S ≤ M), početne pozicije.

IZLAZNI PODATCI

U svakom od P redova ispisati traženi minimalni broj poteza iz teksta zadatka.

PRIMJERI TEST PODATAKA

Ulaz

5 5
...X.
.....
....X
.....
.....
1
-1 1
3
4 4
5 1
3 2

Izlaz

1
5
2

Ulaz

6 4
....
....
..X.
....
....
...X
2
1 0
0 1
4
3 1
2 2
6 3
4 3

Izlaz

2
2
1
2

Ulaz

9 10
..........
..........
..........
..........
.X.....X.X
.X........
.......X..
..........
.....X.X..
3
1 2
1 -2
-1 1
3
5 5
8 8
3 5

Izlaz

2
1
3

Objašnjenje

Prva početna pozicija je (5,5). Do polja sa znakom ‘X’ figurica može doći u dva koraka. Napravimo potez ‘1 2’ i time dolazi na poziciju (6,7). Nakon toga napravimo potez ‘-1 1’ i time figurica dolazi na poziciju (5,8) na kojoj se nalazi znak ‘X’. To je ujedno i minimalan broj poteza.

Druga početna pozicija je (8,8). Do polja sa znakom ‘X’ figurica može doći u jednom koraku. Napravimo potez ‘1 -2’ i time dolazi na poziciju (9,6) na kojoj se nalazi znak ‘X’.

Treća početna pozicija je (3,5). Izvan ploče figurica može stići u tri koraka (i to na više načina). Jedan od načina je da stalno odigravamo potez ‘-1 1’. Figurica tada prelazi preko polja (2,6) i (1,7) te sljedećim potezom završava izvan ploče (0,8).