a614. CPE：Doublets (UVa 10150)

題目描述

若兩個等長單字恰好有一個位置的字母不同，它們就是 doublet。給定字典與多組起終單字，找出最短單字序列：從起點到終點，序列中的每個單字都在字典內，相鄰單字互為 doublet。

輸入格式

先輸入字典，每行一個小寫單字，最多 25143 個，每字長度不超過 16。空白行結束字典。之後每行兩個以空白分隔的查詢單字，讀至檔案結尾。

輸出格式

每個查詢將最短序列的單字各印一行；若有多個最短解，任一皆可。無解輸出 No solution.。兩個查詢的輸出間留一空白行。

題目來源：UVa 10150 — Doublets，CPE 歷屆試題。 原題：https://onlinejudge.org/external/101/10150.pdf

本站測資說明

原題允許輸出任一最短序列，此規則不變。本批測資僅包含無解或最短序列唯一的查詢，以配合逐字比對輸出；若日後加入具有多個最短序列的測資，須使用能驗證路徑合法性與最短長度的語意檢查器。