ARC011 C - ダブレット

問題原文

atcoder.jp

解法

グラフ構築 + BFS + 経路復元、という問題。

グラフ構築

「１文字変えたら相手の文字列になれる」ような , を見つけ、その間に辺を張ってグラフをつくる。
単語の文字数は MAX30文字らしいので、愚直にやっても大丈夫。

BFS

辺のコストが全て１なので、単純なBFSで最短経路長が求められる。
復元できるように「どこから来たか」の情報を格納しながらやる。

経路復元

BFSのときにやった「どこから来たか」の情報を逆に辿りながら復元する。

sample2みたいな最初からゴールしてるやつがあるので注意（だるいので別で分けた）

実装

from collections import deque
start, end = input().split()
N = int(input())
words = [start] + [input() for _ in range(N)] + [end]
G = [[] for _ in range(N + 2)]


# だるいので別処理
if start == end:
    print(0)
    print(start)
    print(end)
    exit()


# グラフ構築
for i, word1 in enumerate(words):
    for j, word2 in enumerate(words):
        diff = 0
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                diff += 1
            if diff > 1:
                break
        else:
            if diff == 1:
                G[i].append(j)


# 復元できるようにしながらBFS
que = deque([0])
froms = [None] * (N + 2)
froms[0] = -1

while que:
    n = que.pop()
    for to in G[n]:
        if froms[to] is not None:
            continue
        que.appendleft(to)
        froms[to] = n


# 答えを計算
if froms[-1] is None:
    print(-1)
else:
    ans_num = 0
    ans_words = []
    marker = N + 1
    while marker != -1:
        ans_num += 1
        ans_words.append(words[marker])
        marker = froms[marker]
    print(ans_num - 2)
    print(*ans_words[::-1], sep="\n")

感想

PASTででそう（雑）