Guliver

Guliver se probudio na otoku okružen malim Liliputancima. Nakon uvodnog natezanja, Liliputanci mu pričaju o svojoj svañi s Blefuščanima, koji žive na susjednom otoku. Malo je poznato da su Liliputanci i Blefuščani jednom živjeli na istom otoku. Nakon što je netko skuhao jaje, uslijedila je svaña oko toga s koje strane ga pojesti. Svaña je poprimila tolike razmjere da su dva naroda odlučila razdvojiti otok, i to na sjevernu i južnu stranu. Začudo, otok je bio pravokutnog oblika te je bio podijeljen u R×S parcela. Neke parcele na otoku su bile potopljene vodom, a stanovnici su odlučili potopiti još neke parcele, i to tako da se nakon potapanja otok razdvoji na barem dva dijela, od kojih jedan dio sadrži cijeli najgornji red (u kojem su nastambe Liliputanaca), a neki drugi cijeli najdonji red (u kojem su nastambe Blefuščana). Dvije nepotopljene parcele pripadaju istom dijelu otoka ako se može doći od jedne do druge pomoću niza koraka, svaki u jednom od četiri glavna smjera (gore, dolje, lijevo, desno), bez da se smoče noge.Povijesni problem o kojem se priča već naraštajima jest koliko je najmanje parcela bilo potrebno potopiti kako bi se otoci razdvojili na opisani način. Napišite program koji računa taj broj.