leaden orbit
The question is CCC 2012 S5
Can anyone please help me find out what the error was? Thanks so much
The AC Code(Both CCC grader and DMOJ):
ROWS, COLS = map(int, input().split())
# extra array to track cats for simplicity
cats = [[False for _ in range(COLS + 1)] for _ in range(ROWS + 1)]
for i in range(int(input())): # cats
r, c = map(int, input().split())
cats[r][c] = True
# add extra row and col to prevent array out of bounds
dp = [[0 for _ in range(COLS + 1)] for _ in range(ROWS + 1)]
dp[1][1] = 1
for r in range(1, ROWS + 1):
for c in range(1, COLS + 1):
if not cats[r][c]:
dp[r][c] += dp[r-1][c] + dp[r][c-1]
print(dp[-1][-1])
The code that AC on DMOJ but not CCC grade:
from functools import cache
directions = [(0, 1), (1, 0)]
r, c = map(int, input().split())
cats = []
for i in range(int(input())):
x, y = map(int, input().split())
cats.append((x, y))
@cache
def dfs(node):
x, y = node
if (x, y) == (r, c):
return 1
if (x, y) in cats:
return 0
total = 0
for dr, dc in directions:
nx, ny = x + dr, y + dc
if 1 <= nx <= r and 1 <= ny <= c:
total += dfs((nx, ny))
return total
print(dfs((1, 1)))
I also manually check the official test case, and the second code also work.
royal forge
