問題概要
問題ページ
-
E - Third Avenue
問題ページへ移動する
問題文
縦 \(H\) マス、横 \(W\) マスの \(2\) 次元グリッドで表された街があります。
上から \(i\) 行目、左から \(j\) 列目のマスの情報が文字 \(a_{i,j}\) により与えられます。 \(a_{i,j}\) は S
, G
, .
, #
, a
~ z
のいずれかです。
#
は入ることができないマスを、a
~ z
はテレポーターのあるマスを表します。
高橋くんははじめ S
のマスにおり、 \(1\) 秒ごとに以下のいずれかの移動を行います。
- 現在いるマスと上下左右に隣り合う、
#
でないマスに移動する。 - 今いるマスと同じ文字が書かれているマスを \(1\) つ選び、そこにテレポートする。この移動は現在いるマスが
a
~z
のいずれかであるとき使える。
高橋くんが S
のマスから G
のマスに移動するのに必要な最短の時間を求めてください。
ただし、どうしても G
のマスにたどり着けない場合は、代わりに -1
を出力してください。
制約
- \(1 \le H, W \le 2000\)
- \(a_{i,j}\) は
S
,G
,.
,#
, 英小文字のいずれか S
のマスとG
のマスはちょうど \(1\) つ存在する
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
h, w = list(map(int, input().rstrip('\n').split()))
a = []
sh, sw, gh, gw = 0, 0, 0, 0
d = [[] for _ in range(28)]
for i in range(h):
ta = list(str(input().rstrip('\n')))
for j in range(w):
ta[j] = ord(ta[j])
if ta[j] == 83:
d[26] += [i, j]
elif ta[j] == 71:
d[27] += [i, j]
elif ta[j] == 46:
continue
elif ta[j] == 35:
continue
else:
d[ta[j] - 97] += [[i, j]]
a.append(ta)
ql = [[0, d[26][0], d[26][1], 83]]
ql = collections.deque(ql)
while True:
if len(ql) != 0:
cost, xv, yv, lst = ql.popleft()
if xv == d[27][0] and yv == d[27][1]:
print(cost)
exit()
wp = []
if 0 <= lst < 26:
wp = d[lst]
d[lst] = []
for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]] + wp:
if 0 <= xv < h and 0 <= yv < w:
if a[xv][yv] != 35:
ql.append([cost + 1, xv, yv, a[xv][yv] - 97])
a[xv][yv] = 35
else:
break
print(-1)
if __name__ == '__main__':
solve()