AtCoder Beginner Contest 151

D - Maze Master

atcoder.jp

コンテスト中に解くことはできませんでした。
クソ萎えの翁。

解法

迷路の解として考えられるルートを全部考える。 スタート地点を1つ決めて、そこからもっとも遠い場所への距離を求める。

左上がスタートの場合
#####
#0..#
#.#.#
#...#
#.#.#
#####

#####
#01.#
#1#.#
#...#
#.#.#
#####


#####
#012#
#1#.#
#2..#
#.#.#
#####

#####
#012#
#1#3#
#23.#
#3#.#
#####

#####
#012#
#1#3#
#234#
#3#.#
#####

#####
#012#
#1#3#
#234#
#3#5#
#####
よって最長距離は5

その右がスタートの場合
#####
#.0.#
#.#.#
#...#
#.#.#
#####

#####
#101#
#.#.#
#...#
#.#.#
#####

#####
#101#
#2#2#
#...#
#.#.#
#####

#####
#101#
#2#2#
#3.3#
#.#.#
#####

#####
#101#
#2#2#
#343#
#4#4#
#####
よって最長距離は4

以下繰り返し

みたいなことをうまい具合に達成できるコードを考える。 最短距離を考える計算がO(HW)、スタート位置の決め方がHW通りなので、計算時間はO(H² W²)。

制約が1≦H, W≦20とゆるいのでこれでも通る。

実装

探索中のIndexErrorを防ぐため迷路の周りを壁で囲む。

import copy
h,w=map(int,input().split())
maze = [['#']+list(input())+['#'] for i in range(h)]
maze.insert(0,['#']*(w+2))
maze.append(['#']*(w+2))

"""
...
.#.
...
.#.
↓
#####
#...#
#.#.#
#...#
#.#.#
#####
"""

迷路とスタート地点の座標を引数に取り、迷路におけるスタート地点からもっとも遠い座標までの距離を返す関数を作る。

def get_max_length_from_start(maze,x,y):
    tmp_maze=copy.deepcopy(maze)
    length=0 #スタート地点からの距離
    searching = [[y,x]]  #スタート地点からの距離がlengthである座標の集合
    while len(searching)!=0:
        next_searching_list=[]
        for point in searching:
            tmp_maze[point[0]][point[1]]='/' #探索済の座標を埋める
            mawari = [
                [point[0]+1,point[1]],
                [point[0]-1,point[1]],
                [point[0],point[1]+1],
                [point[0],point[1]-1]
            ] #探索点の四方をチェック
            next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari)) #四方のうち、道であるものを格納
            if len(next_searching)==0: #末端にいる場合、長さをmax_lengthとして保持
                max_length=length
                continue
            next_searching_list += next_searching
        searching = list(map(list, set(map(tuple, next_searching_list)))) #next_searching_listの重複した要素を排する
        length+=1
    return max_length

迷路中の全部の点に対して最長距離を更新しながら取得していく

ans=0
for y in range(1,h+1):
    for x in range(1,w+1):
        if maze[y][x]=='#':
            continue
        max_length=get_max_length_from_start(maze,x,y)
        ans = max_length if max_length>ans else ans

print(ans)

レート変化

THE 停滞期。