Veronderstel een vlak van roosterpunten met gehele coördinaten. Een route in dit vlak verbindt naburige roosterpunten (horizontaal of verticaal) zonder daarbij zichzelf te snijden of op zijn stappen terug te keren. Een dergelijke route kan op twee manieren beschreven worden.

Ofwel wordt ze omschreven door de opeenvolgende richtingen waarin gestapt wordt. We stellen de vier mogelijke richtingen voor door de letters W (west, naar links), O (oost, naar rechts), N (noord, naar boven) en Z (zuid, naar onder). Op die manier kan de voorbeeldroute die het startpunt met het eindpunt verbindt in onderstaande figuur (links) omschreven worden als de string NNNONNWWWZZW. Het aantal verplaatsingen naar naburige punten die een route maakt, noemen we de lengte van de route. De voorbeeldroute heeft bijvoorbeeld lengte 12.

Een andere omschrijving gaat ervan uit dat het startpunt van de route in het punt $$(0, 0)$$ gelegen is, en lijst de coördinaten op van de opeenvolgende roosterpunten waarlangs de route loopt. Dit wordt hierboven (rechts) geïllustreerd voor de voorbeeldroute. Deze route eindigt in het roosterpunt $$(-3, 3)$$.

Opgave

Wat is de kortste weg die je kan volgen voor een gegeven route, als je hoogstens één sluipweg mag nemen? Enkel rechte sluipwegen die horizontaal of verticaal twee punten van de route met elkaar verbinden zijn toegelaten. Bovendien moeten de twee punten van de route die door de sluipweg verbonden worden, de enige punten zijn die de sluipweg deelt met de route (de sluipweg mag met andere woorden de route niet snijden of er deels mee samenvallen). Onderstaande figuur toont een sluipweg in de voorbeeldroute uit de inleiding. Deze sluipweg levert bovendien een kortste route van lengte 6 op. Geen enkele andere sluipweg levert een kortere route op voor dit voorbeeld.

Gevraagd wordt:

• Schrijf een functie route waaraan een string moet doorgegeven worden. Deze string omschrijft een route aan de hand van de opeenvolgende richtingen waarin gestapt wordt. De functie moet een lijst teruggeven die de gegeven route omschrijft als de coördinaten van de opeenvolgende roosterpunten waarlangs de route loopt, als het vertrekpunt coördinaten $$(0, 0)$$ heeft. Een coördinaat wordt hierbij voorgesteld als een tuple van twee gehele getallen.

• Gebruik de functie route om een functie sluipweg te schrijven waaraan een string moet doorgegeven worden. Deze string omschrijft een route aan de hand van de opeenvolgende richtingen waarin gestapt wordt. De functie moet de lengte van de kortst mogelijke route teruggeven die men kan bekomen door maximaal één sluiproute te nemen in de gegeven route.

Voorbeeld

>>> route("NNNONNWWWZZW")
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (0, 5), (-1, 5), (-2, 5), (-2, 4), (-2, 3), (-3, 3)]
>>> route("ONNNNNNNNWWWWWWWWWNOO")
[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (0, 8), (-1, 8), (-2, 8), (-3, 8), (-4, 8), (-5, 8), (-6, 8), (-7, 8), (-8, 8), (-8, 9), (-7, 9), (-6, 9)]
>>> route("ZZOOOZZZOOZ")
[(0, 0), (0, -1), (0, -2), (1, -2), (2, -2), (3, -2), (3, -3), (3, -4), (3, -5), (4, -5), (5, -5), (5, -6)]

>>> sluipweg("NNNONNWWWZZW")
6
>>> sluipweg("ONNNNNNNNWWWWWWWWWNOO")
17
>>> sluipweg("ZZOOOZZZOOZ")
11

Merk op dat het mogelijk is dat geen enkele sluipweg een kortere route oplevert dan de oorspronkelijke route. Dat is bijvoorbeeld het geval voor het laatste testvoorbeeld.