Leetcode 576 Solution

This article provides solution to leetcode question 576 (out-of-boundary-paths)
Categories:
Tags:
Access this page by simply typing in "lcs 576" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/out-of-boundary-paths

Solution

class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        cache = {}

        def dfs(m, n, N, i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return 1

            if N == 0:
                return 0

            if (i, j, N) in cache:
                return cache[(i, j, N)]

            ans = 0
            ans += dfs(m, n, N - 1, i - 1, j)
            ans += dfs(m, n, N - 1, i + 1, j)
            ans += dfs(m, n, N - 1, i, j - 1)
            ans += dfs(m, n, N - 1, i, j + 1)
            ans %= 10**9 + 7
            cache[(i, j, N)] = ans
            return ans

        return dfs(m, n, N, i, j)