Atcoder DP Problem H - Grid 1 gives RE

help
, ,
1

Hi,

I’ve been trying to solve Atcoder’s dp problem collection. I started doing a problem called “Grid 1” (H - Grid 1) but my solution gave AC on only half of the test cases. Could anyone please help me figure out my mistake?

I’ve defined dp[i][j] as being the total number of ways to reach the i, j position from 0, 0. I’m using 0-based indexing everywhere…

h, w = map(int, input().split())
grid = []

for i in range(h):
    r = input()
    curr = []
    
    for ch in r:
        if ch == ".":
            curr += [0]
        else:
            curr += [1]
    
    grid.append(curr)

def outofbounds(i, j):
    return (i < 0 or j < 0) or (i >= h or j >= w)

dp = [[None for x in range(w)] for y in range(h)]
dp[0][0] = 1

def recursive(i, j):
    if outofbounds(i, j):
        return 0
    elif dp[i][j] is not None:
        return dp[i][j]
    elif grid[i][j] == 1:
        dp[i][j] = 0
        return 0
    else:
        dp[i][j] = recursive(i-1, j) + recursive(i, j-1)
        return dp[i][j]

print(recursive(h-1, w-1))