Dvimatis masyvas

Sveiki, taigi iškilo problemėlė, turiu tokią užduotį ir nesugalvoju algoritmo ar būdo kaip išspręsti ją.

Esame mieste, kurio gatvės sudaro kvadratinį tinklelį. Mieste yra tam tikras skaičius gėlių parduotuvių. Visos

parduotuvės išdėstytos gatvių kampuose. Viename iš gatvės kampų stovi vyras ir galvoja, ar nepadovanoti

žmonai gėlių. Bet vyras yra alkanas ir vedęs jau daugelį metų, todėl gėles pirks tik tuo atveju, jei iki

artimiausios parduotuvės reikės eiti ne daugiau kaip 5 kvartalus. Tačiau mieste vyksta gatvių remonto darbai,

ir kai kurie kvartalai nepraeinami. Kad nevaikščioti veltui, vyras skambina į miesto savivaldybės

informacijos tarnybą ir klausia, ar toli nuo esamo taško yra gėlių parduotuvė. Jei netoli, tai kaip ją pasiekti.

Parašykite programą, kuria galėtų naudotis savivaldybės informacijos tarnybos darbuotojas.

Duomenys tekstiniame faile “Duom3.txt” išdėstyti tokia tvarka:

pirmoji eilutė – matricos dydis (vienas skaičius <= 50), vyro koordinatės (du skaičiai), antroji ir tolimesnės

eilutės - pati miesto matrica. Matricoje duomenys yra simboliai. Kvartalus skiria gatvės, kurios pažymėtos

taškais. Vieną kvartalo kraštinę žymi 3 simboliai: pirmas gatvės kampas (G – yra gėlių parduotuvė, 0 – nėra

gėlių parduotuvės), kliūtis (0 – nėra, 1 – yra), antras gatvės kampas (G – yra gėlių parduotuvė, 0 – nėra gėlių

parduotuvės). Rezultatas turėtų būti atsakymas, ar yra tokia parduotuvė, iki kurios ne daugiau kaip 5

kvartalai. Jei yra tokia parduotuvė, tai reikia pažymėti bent vieną kelią iki jos. Rezultatą parodykite ekrane.

Pastabos. Praėjimas viena kvartalo kraštine laikomas kvartalo įveikimu. Negalima vaikščioti kiemais, nes ten

gali būti plėšikų. Sankryžas galima kirsti tik stačiu kampu.

Pavyzdys:

“Duom3.txt”

11 11 9
G00.000.000
010.010.010
G00.010.010
...........
G00.010.010
010.010.010
G00.010.010
...........
000.000.000
010.010.010
000.000.000

Rezultatas turėtų atrodyti taip:

Parduotuvė yra už 3 kvartalų.
G00.000.000
010.010.010
G00.010.010
...........
G00.010.010
010.010.010
K00.010.010
K..........
KKKKKKKKK00
010.010.K10
000.000.K00 

Gal turite įdėjų ar galite padėti? :)

Galima su grafais išspręst. Kvartalų kampai bus viršūnės. Atstumai tarp gretimų viršūnių esančių tame pačiame kvartale bus 1, o atstumai tarp viršūnių, kurias skiria gatvės - 0. Ir tada jau Dijkstros, A* arba kuris kitas trumpiausio kelio paieškos algoritmas.