競プロ初中級者100問

AOJ1166 迷路と命ず

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

幅優先探索

はじめに

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

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

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

この問題は幅優先探索を用いて解くことができます。

方針

幅優先探索を行うことで最短経路を求めることができます。幅優先探索はキューを用いて実装できますが、ゴールに到達する前にキューが空になった場合は到達不可能ということになります。

この問題のような迷路を解く問題では、移動可能かどうかを判定する際に壁の有無を参照すれば良いです。周囲には全て壁が配置されていることとして、壁の有無の判定を訪問フラグの判定より先に行うことで、配列外参照をケアしなくてよく実装が簡単になります。

コード

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
33
34
35
36
37
38
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

def solve(W,H,ver,hor):
    dist = [ [0]*W for _ in range(H)]
    dist[0][0] = 1
    q = deque()
    q.append((0,0)) # スタート地点をenqueue
    while(q):
        y, x = q.popleft()
        if y==H-1 and x==W-1:
            break
        else:
            for dx, dy in  dxdy:
                if (dx==-1 and ver[y][x]==0) or (dx==1 and ver[y][x+1] == 0) or (dy==-1 and hor[y][x]==0) or (dy==1 and hor[y+1][x]==0): # 通行可能か
                    if dist[y+dy][x+dx] == 0: # 未訪問か
                        q.append((y+dy,x+dx))
                        dist[y+dy][x+dx] = dist[y][x] + 1 # 距離を記録
    return dist[H-1][W-1]
ans = []
while(1):
    W, H = map(int,input().split())
    if W==0 and H==0:
        break
    ver = [] # 垂直方向の壁
    hor = [] # 水平方向の壁
    hor.append([1]*W) # 一番上の壁（スタート地点から始めるので、入口を塞いで問題ない）
    for i in range(2*H-1):
        bar = list(map(int,input().split()))
        if i%2==0:
            ver.append([1]+bar+[1]) # 一番左と右にも壁を設置
        else:
            hor.append(bar)
    hor.append([1]*(W+1)) # 一番下の壁（ゴール地点につけば終了するので、出口を塞いで問題ない）
    ans.append(solve(W,H,ver,hor))

for a in ans:
    print(a)

記事情報

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