Problem statement

https://binarysearch.com/problems/Longest-Matrix-Path-Length/

Solution

Let us use dp(x, y, dy) states here. Each time we can go:

  1. If dy = 0, then we can go up, down, left.
  2. If dy = 1, then we can go right, down.
  3. If dy = 2, then we can go left, down.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m, MINF = len(M), len(M[0]), -float("inf")

        @lru_cache(None)
        def dfs(x, y, dy):
            if x == n: return 0
            if M[x][y] == 1: return MINF

            ans = dfs(x + 1, y, 0) + 1
            if dy == 0:
                ans = max(ans, dfs(x, y, 1))
                ans = max(ans, dfs(x, y, -1))
            elif 0 <= y + dy < m:
                ans = max(ans, dfs(x, y + dy, dy) + 1) 
            return ans

        return max(0, max(dfs(0, y, 0) for y in range(m)))