```
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.