3. naloga

Ograje

Dana je pravokotna karirasta mreža, ki ima h vrstic in w stolpcev. Posamezno polje mreže ima obliko kvadrata in je lahko prazno ali pa je v njem eno od števil 0, 1, 2 ali 3. Na stranice, kjer se stikata dve polji ali pa kjer polje meji na zunanjost mreže, so ponekod postavljene ograje. (Ograja, če je prisotna na neki stranici, pokriva to stranico v celoti, od oglišča do oglišča, ne pa na primer le delno.)

Radi bi preverili, če so ograje postavljene v skladu z naslednjimi pravili:

  1. Število v polju pove, koliko stranic tega polja mora biti ograjenih.
  2. Če je polje prazno, ni predpisano, koliko stranic tega polja mora biti ograjenih (če sploh katera).
  3. Veriga ograj mora tvoriti en sam cikel, ki ne sme biti nikjer prekinjen ali razvejen in se mora zaključiti sam vase.
  4. V mreži mora biti prisotna vsaj ena ograja.

Naslednja slika kaže nekaj primerov; debele črte predstavljajo ograje. Na mreži (a) so ograje postavljene v skladu z vsemi gornjimi pravili, na ostalih mrežah pa ne. Pri (b) je narobe to, da je eno od polj s številom 2 ograjeno s tremi ograjami, moralo pa bi biti z dvema. Podobno je pri (c) polje s številom 0 ograjeno z eno ograjo, ne bi pa smelo biti z nobeno. Pri ostalih primerih ograja ne tvori enega samega cikla, ampak je na razne načine razvejena ali pa tvori več ločenih ciklov, sploh ni sklenjena v cikel in podobno.



Opiši podatkovne strukture, s katerimi bi lahko v svojem programu predstavil stanje mreže (kar vključuje tako števila na poljih kot položaj ograj), nato pa napiši program (ali opiši postopek, če ti je lažje), ki kot vhod dobi w, h in stanje mreže (v takšnih podatkovnih strukturah, kot si jih prej opisal) in preveri, ali so ograje postavljene v skladu z zgoraj opisanimi pravili. Tvoj postopek mora delovati za mreže poljubne velikosti, ne le takšne, karkšne so prikazane na gornji sliki.