AlgoVisual - Interactive Algorithm Visualization

We are tracking Elsa, an arctic fox, through a rectangular snowy field represented by a binary grid, field, where a 1 denotes snowprints and a 0 denotes no snowprints. We know that the fox crossed the field from left to right, so each column has exactly one 1.

Between two consecutive columns, the row of the 1 may remain the same, go up by one, or go down by one. Above the field (above the first row), there is an icy river. Return how close the fox got to the river, in terms of the number of rows between it and the river. Assume that field has at least one row and one column.

Example:

The field from Figure 6.

Snowprints Example

Input:

[
 [0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0],
 [1, 1, 0, 1, 0, 0],
 [0, 0, 0, 0, 1, 1]
]

Output: 1
Explanation: The fox was the closest to the river in column 2 (row index 1).

1def snowprints(field: List[List[int]]) -> int:

2 min_dist = len(field)

3 rows, cols = len(field), len(field[0])

5 for c in range(cols):

6 # In each column, find the row 'r' where field[r][c] == 1

7 for r in range(rows):

8 if field[r][c] == 1:

9 if r < min_dist:

10 min_dist = r

11 break # Found the fox in this column

13 return min_dist