Het Monster van Loch Ness¹ (bijgenaamd Nessie) is een mythisch dier uit de Schotse folklore dat volgens de sage zou leven in het meer Loch Ness².

In juli 2003 maakte de zender BBC het programma “Searching for the Loch Ness Monster³” waarbij met behulp van sonarstralen het monster gezocht werd. Er werd echter geen spoor van Nessie gevonden.

Opgave

Stel dat je het onderzoek wil overdoen op een rooster van n rijen en m kolommen die het meer voorstellen. Zoek nu het minimale aantal sonarzenders dat je nodig hebt om elke positie te observeren. Hou hierbij rekening met de volgende voorwaarden:

• elke sonar neemt één positie in het rooster in; de sonar controleert de eigen positie en de omliggende posities.
• de rand hoeft niet gecontroleerd te worden gezien Nessie zich daar niet kan verbergen.

Links zie je een voorbeeld van een sonar, en de velden die door de sonar gecontroleerd worden. Rechts zie je een mogelijke oplossing op een rooster met 9 rijen en 13 kolommen.

Programmeer een functie minimum_sonar(n, m) die dit minimale aantal retourneert.

Voorbeelden

>>> minimum_sonar(6, 6)
4

>>> minimum_sonar(7, 7)
4

>>> minimum_sonar(9, 13)
12

Bron

Universiteit van Valladolid (UVa), probleem Searching for Nessy.