Županijsko natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) - 4. zadatak

Ledolomac se na djelomično smrznutom Dunavu mora probiti od točke A do točke B.

Mapa rijeke je kvadratna mreža znakova koja se sastoji od n redaka označenih brojevima od 1 do n odozgo prema dolje, te n stupaca označenih brojevima od 1 do n slijeva nadesno.

Neka polja u mapi su zaleđena (označena znamenkom “1”) dok ostala nisu (označena znamenkom “0”).

Ledolomac se može micati u četiri smjera (gore, dolje, lijevo ili desno) te se može kretati i preko slobodnih i preko zaleđenih polja.

Međutim, kretanje po zaleđenim poljima je puno teže pa posada želi naći put od A do B koji sadrži što manje takvih polja.

Dodatno, posada ima na raspolaganju jednu kemijsku bombu koju mogu precizno lansirati bilo gdje na rijeku.

Pomoću bombe dosega k je moguće otopiti sva zaleđena polja unutar jednog kvadratnoga područja veličine k redaka puta k stupaca (koje mora u potpunosti ležati unutar mape).

Zadana je mapa rijeke te q različitih scenarija.

U svakom scenariju j su zadana polja Aj i Bj te doseg bombe kj.

Za svaki scenarij odredite najmanji mogući broj zaleđenih polja koje ledolomac treba prijeći na zadanoj mapi kako bi se probio od Aj do Bj , uz upotrebu jedne bombe dosega kj .

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 2 000) — dimenzije mape.

U j-tom od sljedećih n redova nalazi se niz od točno n znakova “0” ili “1” — j-ti redak mape.

U sljedećem redu nalazi se prirodni broj q (1 ≤ q ≤ 5) — broj scenarija.

U j-tom od sljedećih q redova nalazi se pet prirodnih brojeva k, rAj, sAj, rBj i sBj (1 ≤ kj ≤ n, 1 ≤ rAj, sAj, rBj, sBj ≤ n) — doseg bombe te koordinate (broj retka pa broj stupca) polja Aj i polja Bj u j-tom scenariju.

U svakom scenariju su polja Aj i Bj međusobno različita te niti jedno od njih nije zaleđeno.

Izlazni podaci

Ispišite q redova. U j-ti red ispišite traženi minimalni broj zaleđenih polja u j-tom scenariju

Primjeri test​ podataka

Ulaz

7
1000011
1011111
1111111
1111111
0011111
1100100
1100001
1
2 1 5 6 7

Izlaz

1

Objašnjenje

Pojašnjenje prvog primjera: Ukoliko posada lansira bombu tako da se otopi sav led u kvadratu čiji je gornji lijevi kut polje (4, 2) onda postoji put od A do B koji prolazi kroz samo jedno zaleđeno polje.

Ulaz

8
01111100
10111101
11101110
11010110
11000100
11010111
11101101
01100010
4
2 1 1 8 8
2 1 8 8 1
3 1 1 8 8
5 1 8 8 1

Izlaz

3
2
2
1