競プロ典型 90 問：072 - Loop Railway Plan（★4）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/30
• 結果：解けた
• 時間：45分ぐらい

考えたこと

• 効率的な解法は特に思いつかないし、制約が小さいので全探索か？
• 再帰で全ルートを求める

公式解説

https://twitter.com/e869120/status/1407109731546636289/photo/1

解説を読んだふりかえり

• ちょっと時間はかかったけど、ACできてよかった。
• ビットDPは後で調べよう。(https://atcoder.jp/contests/typical90/tasks/typical90_as が参照されてるけど★6なので保留)

ソース

H,W = [int(x) for x in input().split()]
C = []
for _ in range(H):
    L = input()
    C.append(L)

# pathの末尾からスタートして、長さを返す
def f(path):
    # x,yが末尾(現在の座標)
    x,y = path[-1]
    dX = [0, 0,1,-1]
    dY = [1,-1,0, 0]
    ans = -1 
    # 隣に進む
    for dx,dy in zip(dX,dY):
        # 進んだ座標
        X = x+dx
        Y = y+dy
        # 枠内＆平地ならすすめる
        if (0<=X<W) and (0<=Y<H) and C[Y][X]==".":
            # まだ通ってない場合は進んで再帰
            if not (X,Y) in path:
                path.append((X,Y))
                ans = max(ans, f(path))
                path.pop()
            # 開始位置に戻れる場合もスコア更新
            if (X,Y) == path[0] and len(path)>=4:
                ans = max(ans, len(path))
                # print(path)
    return ans


ans = -1
# 開始地点は全箇所
for x in range(W):
    for y in range(H):
        if C[y][x] == ".":
            path = [(x,y)]
            ans = max(ans, f(path))
print(ans)