First of all, let's get the description of the problem clear.
The input is actually a graph, where each cell is a point in the graph. And each cell is connected to at most 4 cells (less than 4 if the cell is on the edge of the matrix). So we can try to solve this problem using some graph algorithms like BFS, DFS or even some advanced algorithms like DJI.
Think from 3 aspects.
So we can assign height to each points by the following order. First, assign cells whose height can be 1, then 2, 3, etc.
The solution is almost a standard breadth-first search (BFS). First, we initialize a queue where all elements in the queue has height 0. Then we pop points from the queue. Each time if we find a adjacent point which is undefined, we put it into the queue. This keeps that the prior point in the queue always has lower or equal height than later points.
Note:
- Status is_visited for each point is stored in the height matrix as -1.
- Items in the queue is a tuple with 3 values, (<height, x_index, y_index>).
- queue.Queue is a python internal library to support basic first-in first-out (FIFO) queue queue.
import queue
class Solution:
def highestPeak(self, isWater):
rows = len(isWater)
cols = len(isWater[0])
height = [[-1] * cols for _ in range(rows)]
handle_later = queue.Queue()
for i in range(rows):
for j in range(cols):
if isWater[i][j]:
handle_later.put((0, i, j))
height[i][j] = 0
while not handle_later.empty():
h, i, j = handle_later.get()
for neighborI, neighborJ in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
if neighborI < 0 or neighborI >= rows or neighborJ < 0 or neighborJ >= cols:
continue
if height[neighborI][neighborJ] >= 0:
continue
height[neighborI][neighborJ] = h + 1
handle_later.put((h + 1, neighborI, neighborJ))
return height