Out of Boundary Paths

Problem Id: 576 Difficulty: Medium


Intuition

Solution


class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        mod = 10 ** 9 + 7
        grid = [[0] * n for _ in range(m)]
        aux = [[0] * n for _ in range(m)]
        ans = 0
        grid[i][j] = 1
        for _ in range(N):
            for i in range(m):
                ans += grid[i][0] + grid[i][-1]
            for j in range(n):
                ans += grid[0][j] + grid[-1][j]
            for x in range(m):
                for y in range(n):
                    aux[x][y] = 0
                    if x > 0:
                        aux[x][y] += grid[x - 1][y]
                    if y > 0:
                        aux[x][y] += grid[x][y - 1]
                    if x + 1 < m:
                        aux[x][y] += grid[x + 1][y]
                    if y + 1 < n:
                        aux[x][y] += grid[x][y + 1]
                    aux[x][y] = aux[x][y] % mod
            grid, aux = aux, grid
        return ans % mod