AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の72問目である「072 – Loop Railway Plan（★4）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【072 – Loop Railway Plan（★4）】
問題概要
ABC王国には、H行W列のマス目が存在します。各マスは、山のマスか平野のマスのどちらかです。目的は、特定の条件を満たす鉄道路線の最長経路を求めることです。
考察
この問題は、最短経路を求めるのではなく、最長経路を求めるものです。しかし、基本的なアプローチは最短経路問題と同じく、深さ優先探索(DFS)を使用して解くことができます。
鉄道路線の条件
- あるマスを始点として、辺を共有して隣接するマスに移動することをk回 (3≤k) 繰り返し、始点に戻る経路である。
- k回の移動について、移動先はすべて異なる。ただし、始点と終点は同じで良い。
- 経路上に山のマスは存在しない。
解法のポイント
- まず、スタート位置が指定されていないため、すべてのマスをスタート位置として全探索を行います。(今回はgridが16マス以下であるため、全探索が可能)
- 現在の位置から移動できる方向は、上下左右の4通りです。これを利用してDFSを進めます。
- スタート位置からDFSを開始し、再びスタート位置に戻る経路を見つけた場合、その経路の長さを計算し、これまでの最長経路と比較して更新します。
典型解法：深さ優先探索
コード
H,W = map(int, input().split())
grid = []
for i in range(H):
w = input()
grid.append(w)
move_x = [-1,0,1,0]
move_y = [0,1,0,-1]
ans = -1
seen = [[False] * W for _ in range(H)]
def dfs(start, now, seen,dist=0):
now_x, now_y = now
# 各方向に対してDFSを進めていきます
for i in range(4):
nx_x, nx_y = now_x + move_x[i], now_y + move_y[i]
if 0 <= nx_x < H and 0 <= nx_y < W and grid[nx_x][nx_y] == ".":
if (nx_x, nx_y) == start and dist > 2: # スタート地点に戻ってきたら
global ans
ans = max(ans, dist+1) # 現在のパスの長さを計算してansを更新
elif not seen[nx_x][nx_y]: # 未訪問のマスがあれば
seen[nx_x][nx_y] = True # 訪れたとマークして
dfs(start, (nx_x, nx_y), seen,dist+1) # DFSを続けます
seen[nx_x][nx_y] = False # バックトラックします
# 各点からのDFS探索を行います
for i in range(H):
for j in range(W):
# 山のマスはスキップします
if grid[i][j] == "#":
continue
seen = [[False] * W for _ in range(H)] # 訪れたマスを管理するリストを初期化
seen[i][j] = True # スタート地点は訪れたとしてマーク
dfs((i, j), (i, j), seen) # DFSを開始します
print(ans) # 最終的な答えを出力します
まとめ
バックトラックを理解するのがむずい
コメント