白峻1520号:下り坂

今日は白俊1520号の問題を解決しました.
1520号問題はDFSを利用して所与の高さの地図上で下り坂の個数を探す問題である.
問題の説明とI/Oフォーマット

I/O例

質問の回答(概要)

左上から右下までの下り坂数を知るために、下り坂条件を使用してDFSを行います.

例の2、3枚目の図から、経路が重なる可能性があり、時間の複雑さが増すことがわかります.そこで、ある点から到達点までの経路数hを配列に格納し、再びその点に到達したときにh値のみをとり、ブラウズを停止する方法(DP)が選択される.

Pythonコード

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
M, N = map(int, stdin.readline().rstrip().split())
m = []
for _ in range(M):
    m.append(list(map(int, stdin.readline().rstrip().split())))

done = [[0] * N for _ in range(M)]
visited = [[False] * N for _ in range(M)]


def dfs(y, x):
    now = m[y][x]
    result = 0

    if y == M-1 and x == N-1:
        return 1

    if y < M-1:
        if m[y+1][x] < now:
            if done[y+1][x] > 0:
                result += done[y+1][x]
            elif not visited[y+1][x]:
                result += dfs(y+1, x)

    if x < N-1:
        if m[y][x+1] < now:
            if done[y][x+1] > 0:
                result += done[y][x+1]
            elif not visited[y][x+1]:
                result += dfs(y, x+1)

    if y > 0:
        if m[y-1][x] < now:
            if done[y-1][x] > 0:
                result += done[y-1][x]
            elif not visited[y-1][x]:
                result += dfs(y-1, x)

    if x > 0:
        if m[y][x-1] < now:
            if done[y][x-1] > 0:
                result += done[y][x-1]
            elif not visited[y][x-1]:
                result += dfs(y, x-1)

    visited[y][x] = True
    done[y][x] = result
    return result


print(dfs(0, 0))

質問の回答(レビュー)
初めて問題を見たとき、問題は簡単だと思った.
単純にアレイの0,0点から,各点の上下左右にDFSを実行すれば,問題を解決できる.
そう考えて実施した結果、タイムアウトとなりました.
タイムアウト問題を解決するために,重複する可能性があるかどうかを考慮した.
多くの場合、シャベルで取り除いてみました
特定の経路で右下に到達した場合.
パスのあるポイントにアクセスすると、右下隅にも到達できることに気づきました.
例えば、例(50、45、37、32、20、17、15、10)の経路はhである.
hを通って右下の10に着きます.
以降hに到達する45,37,32,20,17,15のいずれかの地点では,hの経路に沿っていれば10に到達できるので,以降の経路を探知する必要はない.
そう思う.
まずMxN配列アクセスを作成する
経路hを介して右下隅に到達すると、経路hのすべての点にアクセスするのがtrueとなる.
また、DFSがアクセス値trueのポイントにアクセスすると、H値が1増加し、ブラウズが停止します.
問題は、実施後にテストケースを実行した結果、H値が答えより小さいことが分かったことです.
考えてみれば,アクセス値がtrueの場所では,到着点に通じる経路が2つ以上ある.したがって,配列アクセスをブール配列ではなくint配列に設定することで問題を解決できる.