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