Državno natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 1. zadatak - 2. dan

U jednom našem obalnom gradu postoji tvrtka „Dižemo sve d.o.o“. Spomenuta se tvrtka bavi utovarom teretnih kontejnera u brodove. Tvrtka ima dva radnika koji upravljaju dvjema dizalicama. Njihov zadatak je u što kraćem roku utovariti sve kontejnere, s tim da svaka dizalica prenosi jedan po jedan kontejner.

Zadana je kvadratna mreža na kojoj se nalaze znakovi '.' koji predstavljaju prazan prostor i znakovi i '#' koji predstavljaju zapreku preko koje se dizalica ne može kretati.

Na početku radnog vremena obje se dizalice nalaze u gornjem lijevom uglu mreže (na položaju (0,0)). Ruka dizalice može se pomicati samo u smjerovima paralelnima s rubovima mreže (gore, dolje, lijevo i desno). Za pomicanje s jednog polja na drugo potrebna je jedna sekunda, a vrijeme potrebno za podizanje i spuštanje kontejnera je zanemarivo. Dizalice su neovisne jedna o drugoj, što znači da se mogu nadi na istom polju u isto vrijeme.

Za svaki od kontejnera zadan je početni položaj i položaj na koji ga je potrebno premjestiti. Vaš zadatak je izračunati koliko je najmanje vremena potrebno za prebaciti sve kontejnere, tako da radnici mogu što prije otidi prezalogajiti kakav brzi obrok

ULAZNI PODACI

U prvom retku se nalaze cijeli brojevi N i M ( 1 ≤ N, M ≤ 15 ), koji predstavljaju širinu i visinu kvadratne mreže.

U slijededih N redaka se nalazi po M znakova koji prikazuju prepreke ('#') i slobodan prostor ('.') u mreži.

Potom, u idudem se retku nalazi broj K ( 1 ≤ K ≤ 15 ), koji predstavlja broj kontejnera koje je potrebno premjestiti. Nakon toga, u sljededih K redaka se nalaze po četiri broja X1, Y1, X2 i Y2 ( 1 ≤ X1, Y1, X2, Y2 ≤ 15 ), koji predstavljaju položaj u mreži na kojem se kontejner nalazi i položaj na kojeg ga je potrebno premjestiti. Oba spomenuta položaja kontejnera uvijek de biti položaji slobodnog prostora u kvadratnoj mreži i mapa de biti takva da obje dizalice mogu dodi do tih položaja.

IZLAZNI PODACI

U prvi i jedini redak ispisati jedan cijeli broj koji predstavlja najkrade mogude vrijeme, u sekundama, u kojem radnici mogu premjestiti sve kontejnere.

PRIMJERI TEST PODATAKA

ulaz

3 3
...
.#.
.#.
2
1 1 3 3
1 3 3 1

izlaz

4

ulaz

4 3
..#
#..
.#.
...
3
1 1 2 3
3 1 4 2
4 1 3 3

izlaz

10

ulaz

4 4
....
#..#
#...
#..#
4
1 1 4 2
4 3 2 2
2 3 1 4
4 2 3 4

izlaz

11