【2025 年 3 月月赛赛题 D 题解】交错路径
原题链接
思路
动态规划记录位置、方向、转向次数。状态转移时根据移动方向是否变化更新转向次数。
std
MOD = 10**9+7
n, m, t = map(int, input().split())
grid = [input().strip() for _ in range(n)]
if grid[0][0] == '#' or grid[-1][-1] == '#':
print(0)
exit()
# dp[i][j][d][k]: 位置(i,j)方向d（0右，1下）转向k次的方案数
dp = [[[[0]*(t+1) for _ in range(2)] for __ in range(m)] for ___ in range(n)]
# 初始化第一步
if m > 1 and grid[0][1] == '.':
dp[0][1][0][0] = 1
if n > 1 and grid[1][0] == '.':
dp[1][0][1][0] = 1
for i in range(n):
for j in range(m):
if grid[i][j] == '#':
continue
for d in range(2):
for k in range(t+1):
curr = dp[i][j][d][k]
if curr == 0:
continue
# 向右
if j+1 < m and grid[i][j+1] == '.':
new_d = 0
new_k = k + (d != new_d)
if new_k <= t:
dp[i][j+1][new_d][new_k] = (dp[i][j+1][new_d][new_k] + curr) % MOD
# 向下
if i+1 < n and grid[i+1][j] == '.':
new_d = 1
new_k = k + (d != new_d)
if new_k <= t:
dp[i+1][j][new_d][new_k] = (dp[i+1][j][new_d][new_k] + curr) % MOD
res = 0
for d in range(2):
res = (res + dp[n-1][m-1][d][t]) % MOD
print(res)
【AI 提供】数据生成代码
import random
n, m = 5, 5
t = random.randint(0, 10)
print(n, m, t)
grid = [['.' for _ in range(m)] for __ in range(n)]
# 随机放置障碍，保证起点终点畅通
for i in range(n):
for j in range(m):
if (i,j) == (0,0) or (i,j) == (n-1,m-1):
continue
if random.random() < 0.2:
grid[i][j] = '#'
for row in grid:
print(''.join(row))
【实际上】数据生成代码
import random
for case in range(1, 11):
n, m = 5, 5
t = random.randint(0, 10)
print(n, m, t)
grid = [['.' for _ in range(m)] for __ in range(n)]
# 随机放置障碍
for i in range(n):
for j in range(m):
if random.random() < 0.2:
grid[i][j] = '#'
with open(f'd{case}.in', 'w') as f:
for row in grid:
print(''.join(row), file=f)
with open(f'd{case}.out', 'w') as f:
MOD = 10**9+7
if grid[0][0] == '#' or grid[-1][-1] == '#':
print(0)
continue
# dp[i][j][d][k]: 位置(i,j)方向d（0右，1下）转向k次的方案数
dp = [[[[0]*(t+1) for _ in range(2)] for __ in range(m)] for ___ in range(n)]
# 初始化第一步
if m > 1 and grid[0][1] == '.':
dp[0][1][0][0] = 1
if n > 1 and grid[1][0] == '.':
dp[1][0][1][0] = 1
for i in range(n):
for j in range(m):
if grid[i][j] == '#':
continue
for d in range(2):
for k in range(t+1):
curr = dp[i][j][d][k]
if curr == 0:
continue
# 向右
if j+1 < m and grid[i][j+1] == '.':
new_d = 0
new_k = k + (d != new_d)
if new_k <= t:
dp[i][j+1][new_d][new_k] = (dp[i][j+1][new_d][new_k] + curr) % MOD
# 向下
if i+1 < n and grid[i+1][j] == '.':
new_d = 1
new_k = k + (d != new_d)
if new_k <= t:
dp[i+1][j][new_d][new_k] = (dp[i+1][j][new_d][new_k] + curr) % MOD
res = 0
for d in range(2):
res = (res + dp[n-1][m-1][d][t]) % MOD
print(res, file=f)
