Speleologie is een tak van de aardwetenschappen die zich bezighoudt met de studie van grotten. Hoewel speleologie een serieuze wetenschap is, komt er bij het verkennen van grotten ook een element van sportiviteit, avontuur en moed kijken. Het verkennen van grotten, zeker als zij nog onvolledig bekend zijn, is zeker niet zonder gevaar en vereist vaardigheid en training.

Als wetenschap bestudeert de speleologie onder andere de geologie (het ontstaan van gesteentelagen, grotten en druipsteen), de hydrologie (onderaardse waterlopen), de biologie (de fauna en flora in een grot), de paleontologie (overblijfselen van uitgestorven dieren in grotten) en de archeologie (grotschilderingen en werktuigen uit de prehistorie). Ook de geologie van streken waar grotten voorkomen is onderwerp van studie. De speleologie als sport kunnen we vergelijken met de bergsport, omdat voor een groot deel dezelfde technieken en materialen gebruikt worden.

Opgave

Als onderdeel van je speleologietraining krijg je de plattegrond van een grot die bestaat uit een aantal zalen. De zalen van de grot zijn gerangschikt in een rechthoekig \(m \times n\) rooster met \(m\) rijen en \(n\) kolommen. De grot heeft slechts één ingang en één uitgang, en vanuit elke zaal kan je naar elk van de naburige zalen ten noorden, zuiden, oosten en westen, tenzij je daarbij tegen de rand van de grot botst. Je opdracht bestaat erin een geldige doorgang te vinden die vertrekt vanaf de zaal waar de ingang van de grot gelegen is, en steeds loopt via een naburige zaal totdat de zaal bereikt wordt waar de uitgang van de grot gelegen is. Hierbij mag elke zaal hoogstens één keer bezocht worden. Bovendien bevat de plattegrond ook aanwijzingen hoeveel zalen de doorgang moet passeren op elke rij en kolom van het rooster.

Als voorbeeld krijg je hieronder de plattegrond van een grot, waarvan de zalen gerangschikt zijn in een \(5 \times 5\) rooster. Om makkelijk naar de zalen te kunnen verwijzen, nummeren we de rijen oplopend van noord naar zuid en de kolommen van west naar oost, waarbij we steeds beginnen nummeren vanaf nul (grijze getallen op de voorbeeld plattegrond). De grot heeft een ingang in zaal (0,0) en een uitgang in zaal (3, 4). We beschrijven een doorgang als een opeenvolging van letters die aangeven welk van de naburige zalen in een volgende stap bezocht wordt: N (noord), Z (zuid), O (oost) of W (west).

Plattegrond van een grot met 5 rijen en 5 kolommen, een ingang in cel (0, 0) en een uitgang in cel (3, 4). De doorgang OZWZZOONOZO (midden) is een doorgang die leidt naar de uitgang, waarbij het aantal passages doorheen de rijen en kolommen van de plattegrond worden aangegeven in het groen. De doorgang OOZZWW (links) leidt niet naar de uitgang. De doorgang OOZWWW (rechts) botst tegen de rand van de grot.

De doorgang OZWZZOONOZO (middelste plattegrond van de figuur) is een doorgang die vanaf de ingang leidt naar de uitgang, waarbij het aantal passages doorheen de rijen en kolommen van de plattegrond wordt aangegeven in het groen. Zo zijn er bijvoorbeeld 2 passages door de meest noordelijke rij en 4 passages door de meest westelijke kolom. Bovendien bezoekt deze doorgang elke zaal hoogstens één keer. De doorgang OOZZWW (linkse plattegrond) is niet geldig omdat die niet naar de uitgang leidt. De doorgang OOZWWW (rechtse plattegrond) is eveneens ongeldig, omdat er tegen de rand van de grot wordt gebotst.

Je opdracht bestaat erin een klasse Grot te schrijven waarvan elk object de plattegrond van een grot voorstelt. De grot bestaat uit een aantal zalen die gerangschikt zijn in een rechthoekig \(m \times n\) rooster. Naast de posities van de ingang en uitgang, bevat de map ook aanwijzingen hoeveel zalen een geldige doorgang moet passeren op elke rij en kolom van het rooster.

Definieer een klasse Grot waarmee de plattegrond van grotten kan vastgelegd worden, alsook het gewenste aantal passages op elke rij en kolom van het rooster. Aan de constructor moeten vier argumenten doorgegeven worden, waarbij elk argument een reeks (Array) met natuurlijke getallen (Number) is. Het eerste argument bevat \(m\) getallen die aangeven hoeveel passages de gezochte doorgang moet hebben door elke rij (van noord naar zuid) van het rooster. Het tweede argument bevat \(n\) getallen die aangeven hoeveel passages de gezochte doorgang moet hebben door elke kolom (van west naar oost) van het rooster. De laatste twee argumenten bevatten het rijnummer \(r\) en kolomnummer \(k\) van de zalen waar respectievelijk de ingang en de uitgang van de grot gelegen zijn. De constructor moet een Error opwerpen met de boodschap ongeldige plattegrond als minstens één van de volgende voorwaarden niet voldaan is:

Zorg ervoor dat een grot (Grot) minstens over de volgende methoden beschikken, waarmee kan nagegaan worden of een gegeven doorgang al dan niet geldig is.

Voorbeeld

> var grot = new Grot([2, 2, 3, 5, 0], [4, 3, 2, 2, 1], [0, 0], [3, 4]);

> grot.doorgang('OOZZWW');
[[0, 0], [0, 1], [0, 2], [1, 2], [2, 2], [2, 1], [2, 0]]
> grot.passages('OOZZWW');
[[3, 1, 3, 0, 0], [2, 2, 3, 0, 0]]
> grot.geldigeDoorgang('OOZZWW');
false

> grot.doorgang('OZWZZOONOZO');
[[0, 0], [0, 1], [1, 1], [1, 0], [2, 0], [3, 0], [3, 1], [3, 2], [2, 2], [2, 3], [3, 3], [3, 4]]
> grot.passages('OZWZZOONOZO');
[[2, 2, 3, 5, 0], [4, 3, 2, 2, 1]]
> grot.geldigeDoorgang('OZWZZOONOZO');
true

> grot.doorgang('OOZWWW');
Error: botst tegen rand
> grot.passages('OOZWWW');
Error: botst tegen rand
> grot.geldigeDoorgang('OOZWWW');
Error: botst tegen rand

> var grot = new Grot([2, 2, 3, 6, 0], [4, 3, 2, 2, 1], [0, 0], [3, 4]);
Error: ongeldige plattegrond

> var grot = Grot([2, 2, 3, 5, 0], [4, 3, 2, 2, 1], [1, 1], [3, 4]);
Error: ongeldige plattegrond