[Baekjoon] 1520. 下り坂[G 4]

📚 質問する

https://www.acmicpc.net/problem/1520

📖 に答える

DPタワーで解けました.
DFS backtrackingを使用し、DPの値を格納して使用します.
冒頭の部分を入れて再鬼を叫び、引き続き再鬼に乗って入り、arr(-1, -1)人の最後の再鬼まで中から救い始める.
上から下へと解決すると、コードが簡潔になります.
求める過程で分岐点で使用する値を使用するためにDPを使用する.
4方向から探索するのでデルタ探索を利用して、どうせ過去の場所に戻るなら上り坂なので単独で処理する必要はありません.
探して道がない場合は0を返し、retを0に初期化して計算します.

📒 コード#コード#

def recur(x, y):
    if x == m - 1 and y == n - 1:
        return 1
    ret = 0
    if dp[x][y] != -1:
        ret = dp[x][y]
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and arr[x][y] > arr[nx][ny]:
                ret += recur(nx, ny)
        dp[x][y] = ret
    return ret


m, n = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dp = [[-1] * n for _ in range(m)]

print(recur(0, 0))

🔍 結果