D - 経路 https://atcoder.jp/contests/abc037/tasks/abc037_d

abc037_d.py

import sys

sys.setrecursionlimit(10**7)
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
MOD = 10**9 + 7


def dfs(x, y):
    if dp[y][x] != 0:
        return dp[y][x]
    if dp[y][x] == 0:
        dp[y][x] = 1
    for dx, dy in dir:
        nxt_x = x + dx
        nxt_y = y + dy
        if nxt_x < 0 or nxt_y < 0 or nxt_x >= W or nxt_y >= H:
            continue
        if a[nxt_y][nxt_x] <= a[y][x]:
            continue
        dp[y][x] += dfs(nxt_x, nxt_y)
        dp[y][x] %= MOD
    return dp[y][x]


H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
dp = [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        dfs(x, y)
ans = 0
for i in range(H):
    ans += sum(dp[i])
print(ans % MOD)