| Given a grid graph \(G\). This a graph whose node set is the set of all ordered pairs of naturals number \((i,j)\), where \(0\leq i,j \lt n\); the nodes \((i,j)\) and \((k,l)\) are joined by an edge if and only if $$ | i-k | + | j-l | =1$$. |
Every node \(v\) in \(G\) is labeled by a integer \(x_v\). You may assume that the numbers labeling the nodes are distinct. A node \(v\) of \(G\) is a local minimum if the label \(x_v\) is less than the lable \(x_w\) for all nodes \(w\) that are joined to \(v\) by an edge.
Design and implement an algorithm that finds a local minimum in a given grid graph \(G\) by checking only \(O(n)\) nodes. (Note that \(G\) has \(n^2\) nodes.)
*Hint: Try to reduce the \(n \times n\) problem to a \(n/2 \times n/2\) problem in \(O(n)\) time.
Write a Python function findminimum(matrix:list) that finds a local minimum in a given graph.
The graph is represented as a matrix, which is represented by a list of lists, e.g.,
[[129, 175, 115, 31, 134, 4, 102],
[137, 70, 140, 142, 38, 154, 158],
[79, 173, 60, 141, 182, 69, 13],
[68, 48, 147, 99, 157, 24, 67],
[94, 0, 86, 76, 51, 191, 28],
[160, 177, 120, 183, 114, 36, 105],
[143, 33, 104, 167, 27, 159, 54]]
This matrix is the same as the following one:
\[\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}\]The local minima have been highlighted in red.
>>> findminimum([[129, 175, 115, 31, 134, 4, 102],[137, 70, 140, 142, 38, 154, 158],[79, 173, 60, 141, 182, 69, 13],[68, 48, 147, 99, 157, 24, 67],[94, 0, 86, 76, 51, 191, 28],[160, 177, 120, 183, 114, 36, 105],[143, 33, 104, 167, 27, 159, 54]])
70 # All other minima will also be accepted in the tests