競プロ初中級者100問

JOI2009予選D 薄氷渡り

この記事で使うアルゴリズム

深さ優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_f

この問題は動的計画法を用いて解くことができます。

ポイント

  • 動的計画法は再帰によって実装できます。
  • 配列の周囲を0で埋めると、配列外参照かを判定する条件分岐を書かなくてよく、実装が楽になる場合があります。
  • 再帰関数の最初に、mp[n][m] = 0として同じパス内で同じ区画を再度訪問しないようにします。関数から抜ける際に、mp[n][m] = 1としてそれを解除します。
    • 異なるパスでは再度訪問しても問題がないためです。

      コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
sys.setrecursionlimit(10**7)
dxdy = ((0,1),(0,-1),(1,0),(-1,0))
M = int(input())
N = int(input())

mp = []
mp.append([0]*(M+2))
for n in range(N):
    line = list(map(int, input().split()))
    mp.append([0]+line+[0])
mp.append([0]*(M+2))

ans = 0
def dfs(n,m,d):
    global ans # グローバル変数
    if mp[n][m] == 0:
        return
    if ans < d:
        ans = d
    
    mp[n][m] = 0
    for dx, dy in dxdy:
        next_n = n + dy
        next_m = m + dx
        dfs(next_n, next_m, d+1)
    mp[n][m] = 1

for n in range(1,N+1):
    for m in range(1,M+1):
        dfs(n,m,1)
print (ans)

記事情報

  • 投稿日：2020年6月2日
  • 最終更新日：2020年6月22日