Edit

【pythonでABC184を解説】E - Third Avenue

問題概要

問題ページ

E - Third Avenue
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()

-Edit
-