Supershipの名畑です。少し前の話になりますがこのマンガがすごい！2023を見て、今年もオトコ編は集英社が多いなという素直な印象を持ちました。ランクインしているあかね噺は古典芸能である落語をジャンプの文法に見事に落とし込んでいて面白くて好き。
はじめに
アルゴリズム実技検定(PAST)の過去問シリーズです。
第11回のI問題になります。
A問題からここまで解ければ合計で64点なので中級となります。
前にも引用させていただいたAtCoder社長の高橋様のつぶやき(2019年時点ですが)によるとこれで緑相当でしょうか？
AtCoderで緑の私は分相応に第11回はいったんここまでとして、次からは別の回のA問題から順番にやっていこうかと思います。
それと競プロ典型 90 問も解答例を挙げていこうかと思っています。
「そもそもアルゴリズム実技検定ってなんですか？」という方はこちらの記事を合わせてご覧いただけますと幸いです。
第11回 I問題 お片付け
問題
言語
- PyPy3 (7.3.0)
今回もPython(3.8.2)だとTLEなのでPyPyを使いました。
常にPyPyにすればいいんですが、なんか負けた気がしてできる限り使わないようにしています（深い意味はない）。
解答例
全経路を探索する場合においては、出発点から離れたところを目指して行き止まりで引き返すということを繰り返す深さ優先探索(DFS)、近いところを順番に見ていく幅優先探索(BFS)、この二つは代表的です。
今回は最短経路を求める問題のため、計算量的に幅優先探索(BFS)を用います。
from collections import deque # deque使うのでimport
H, W = map(int, input().split())
# s,a,gはそれぞれ1座標のみを持つ
s = [0, 0]
a = [0, 0]
g = [0, 0]
# [H][W]の2次元配列
# 壁があればTrue
wall = [[False] * W for i in range(H)]
for i in range(H):
S = list(input())
for j in range(0, W):
if S[j] == 's':
s = [i, j]
elif S[j] == 'a':
a = [i, j]
elif S[j] == 'g':
g = [i, j]
elif S[j] == '#':
wall[i][j] = True
# [すぬけ君の縦位置][すぬけ君の横位置][荷物の縦位置][荷物の横位置]の4次元配列
# 格納される値はそこまでの最短行動回数で、初期値は充分に大きければいいので無限大にしてあります
inf = float("inf") # 無限大
status = [[[[inf for l in range(W)] for k in range(H)] for j in range(W)] for i in range(H)]
# 初期状態を行動回数0とする
status[s[0]][s[1]][a[0]][a[1]] = 0
# 回答
ans = inf
# 上、右、下、左の移動量
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
# 次の行動を格納するdeque
que = deque()
# 初期位置からの4方向を格納
# 格納されるのはすぬけ君の縦位置、すぬけ君の横位置、荷物の縦位置、荷物の横位置、移動方向(上右下左）、ここまでの行動回数
for i in range(0, 4):
que.appendleft([s[0], s[1], a[0], a[1], i, 0])
# queが空になるまで繰り返す
while len(que):
val = que.popleft()
sy, sx, ay, ax, d, count = val # わかりやすいように配列をアンパック
# ゴール到達の最短行動回数と比較
if count > ans - 1:
continue
dy = direction[d][0] # 縦移動距離
dx = direction[d][1] # 横移動距離
sy += dy
sx += dx
count += 1
if sy < 0 or sy > H - 1 or sx < 0 or sx > W - 1: # すぬけ君が枠の外に出る
continue
if wall[sy][sx]: # 移動先が壁
continue
if sy == ay and sx == ax: # 移動先が荷物
ay += dy
ax += dx
if ay < 0 or ay > H - 1 or ax < 0 or ax > W - 1: # 枠の外に荷物が出る
continue
if wall[ay][ax]: # 移動先が壁
continue
if ay == g[0] and ax == g[1]: # 移動先がゴール
ans = min(ans, count)
continue
if count < status[sy][sx][ay][ax]: # 過去の同一状態の行動回数を確認
status[sy][sx][ay][ax] = count
for d in range(0, 4): # 4方向への移動をqueに格納
que.append([sy, sx, ay, ax, d, count])
if ans == inf:
print(-1)
else:
print(ans)
このコードで2secぎりぎりでした。
この問題は4secまでは許容されるのでまだ余裕はありますが。
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。
是非ともよろしくお願いいたします。