How to find the path of least sum, moving right and down in a binary matrix

Question

I have a binary matrix. Each column corresponds to a vertex in a graph. If I walk along the path (starting on the "col 1" vertex, then moving on to "col 2" etc.), I have to pay some fines. But since there are only so many police officers on the path, I can wait for some time until there is no police officer remaining on the next vertex, then go over. To clarify, the following matrix (first row is the "title" row):

Encodes that I will pay if I am on A after waiting an extra 1, 2 or 3 hours before that point; on B, I will pay after 2 or 3 extra hours; on C, I will pay after 0 or 3 hours; on D, I will pay if I wait 1 or 3 hours.

As such, the optimal path here is "move to B, wait 1 hour, move to C, wait 1 hour, move to D", with total cost 0. (this path is marked with "X" on the following)

A B C D
X X 1 0
1 X X 1
1 1 X X
1 1 1 1
0 0 0 0

However, achieving 0 is not always possible, and I am only interested in one of the paths of minimal sum that goes from the top left entry to the right column.

How can I generate such a path efficiently?

The naive algorithm "generate all paths, find the minimum" works in exponential time, which doesn't feel optimal to me.

I thought of using a DP approach, but I was unable to formulate one that did not break on some cases, whether I try to add line-by-line or column-by-column

user_9350720 · Answer

Let's start with a simple question. Let's say you're at row i, column j (i.e. cell (i,j)) of the matrix. What choices do you have for the next step?

Since we're moving column-wise, j becomes j+1. But for the row, you can greedily choose the row which pays the minimum fine. That is, you can pick i' in range (i+1, row_count) such that fine(i,j) is minimum. (Note: since the row represents points in time, you can't go from row i to i-1, effectively shortening our search space).

The algorithm:
(n = number of rows = len(matrix), m = number of columns)

For the rightmost column, we don't have any further paths, so no modification needed
For columns m-1 to 1, the minimum fine for cell (i,j) will be

fine(i,j) = (matrix[i][j] == 1) + (min_value in matrix[i][j+1] to matrix[n][j+1])

Min path cost will be matrix[0][0], from where you trace the path by checking the min values from each column.

The last point we need to cover is, how to get min_value in matrix[i][j+1] to matrix[n][j+1] in step 2? If you traverse from row n to row 1, the task basically boils down to keeping a track of the smallest element visited yet, which can be done using a simple variable/counter.

The approach requires no extra space (since we modify the given matrix), and O(M*N) time complexity.

How to find the path of least sum, moving right and down in a binary matrix

1 Answers