Short solution - Each path needs at most one turn


  • 11
    def updateMatrix(self, matrix):
        answer = [[10000 * x for x in row] for row in matrix]
        for _ in range(4):
            for row in answer:
                for j in range(1, len(row)):
                    row[j] = min(row[j], row[j-1] + 1)
            answer = map(list, zip(*answer[::-1]))
        return answer
    

    Based on @qswawrq's solution which only considers down/right paths (meaning a combination of only down and right moves, from some 0 to some 1) and up/left paths. When I realized why that works, I realized that we don't even need paths like down,right,down,right. We can instead go just down,down,right,right or right,right,down,down. Just one turn (change of direction). It's the same length, and all of the intermediate cells must be 1 because otherwise down,right,down,right wouldn't have been an optimal path in the first place.

    So in my solution I simply optimize in each direction, one after the other. For this I "optimize rightwards" and "rotate the matrix by 90 degrees" four times. Then I have covered every pair of directions, which is enough to cover every straight path and every single-turn path.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.