Zij gegeven een graaf \(G\) bestaande uit een \(n\times n\) rooster, m.a.w.\ een graaf bestaande uit cellen \((i,j)\) met \(1\leq i,j \leq n\), waarbij een cel \((i,j)\) verbonden is met een cel \((k,l)\) als en slechts als \(|i-k|+|j-l|=1\). Elke cel \(v\) in \(G\) is gelabeld met een gehele waarde \(x_v\). Je mag veronderstellen dat de waarden die de cellen labelen, allemaal verschillend zijn. Een cel \(v\) van \(G\) is een lokaal minimum als het label \(x_v\) kleiner is dan het label \(x_w\) voor alle cellen \(w\) die met \(v\) verbonden zijn.

Ontwerp en implementeer een algoritme dat een lokaal minimum in \(G\) bepaalt door slechts \(O(n)\) cellen van \(G\) te bevragen. (Merk op dat \(G\) \(n^2\) cellen heeft.)

Hint: Probeer het \(n \times n\) probleem te herleiden naar een \(n/2 \times n/2\) probleem in \(O(n)\) tijd.

Opgave

Schrijf een klasse MijnRoosterZoeker die de interface RoosterZoeker¹ implementeert. Deze klasse moet een methode int zoek(Rooster rooster) implementeren die, een gegeven Rooster² binnenkrijgt en een lokaal minimum teruggeeft.

De klasse Rooster bevat 3 methodes:

• int get(x,y) geeft het element op rij x en kolom y van het gegeven rooster terug.
• int getbreedte() geeft de breedte van het rooster terug.
• int gethoogte() geeft de hoogte van het rooster terug.

Voorbeeld

De graaf wordt voorgesteld door een matrix, bijvoorbeeld:

\[\begin{pmatrix} \color{red}{129} & 175 & 115 & \color{red}{31} & 134 & \color{red}{4} & 102 \\ 137 & \color{red}{70} & 140 & 142 & \color{red}{38} & 154 & 158 \\ 79 & 173 & \color{red}{60} & 141 & 182 & 69 & \color{red}{13} \\ 68 & 48 & 147 & 99 & 157 & \color{red}{24} & 67 \\ 94 & \color{red}{0} & 86 & 76 & \color{red}{51} & 191 & \color{red}{28} \\ 160 & 177 & 120 & 183 & 114 & \color{red}{36} & 105 \\ 143 & \color{red}{33} & 104 & 167 & \color{red}{27} & 159 & \color{red}{54} \end{pmatrix}\]

De lokale minima zijn hier in het rood geplaatst.