Submission #722859

---

Source Code Expand

def dfs(x,y):
    if memo[y][x] >= 0:
        return memo[y][x]
    dxdy = [(1,0), (0,1), (-1,0), (0,-1)]
    ret = 0
    for dx, dy in dxdy:
        xdx = x+dx
        if 0 <= xdx < W and 0<= y+dy < H and B[y][x] < B[y+dy][xdx]:
            if memo[y+dy][xdx] >= 0:
                hoge = memo[y+dy][xdx]
            else:
                hoge = dfs(xdx,y+dy)
            memo[y+dy][xdx] = hoge
            ret += hoge + 1
    memo[y][x] = ret
    return ret
import sys
sys.setrecursionlimit(1000000)
H,W = map(int,input().split())
B = [list(map(int,input().split())) for i in range(H)]
memo = [[-1]*W for j in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        ans += dfs(w,h)
print((ans + H*W) % (1000000007))

Submission Info

Judge Result