概要
ある単語について、文字を一文字置換する操作が許される。
与えられた辞書を使って、start から last まで変換するときの手順を求めよ。
解法
単語をノード、遷移をエッジとしたグラフを考えます。
このグラフに対して BFS (辺コストが全て 1 であるので Dijkstra でなくてよい)をし、経路復元をすると求まります。
コード
typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int,int> PII; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) #define MP( a, b ) make_pair( ( a ), ( b ) ) #define fst first #define snd second const int INF = INT_MAX / 4; bool able( const string &a, const string &b ) { int count = 0; REP( i, 0, a.size() ) { count += a[i] != b[i]; } return count == 1; } VI solve( const VVI &G ) { const int N = G.size(); VI dist( N, INF ); dist[0] = 0; VI prev( N ); queue< PII > que; que.push( MP( 0, 0 ) ); while ( !que.empty() ) { auto cur = que.front(); que.pop(); REP( i, 0, G[ cur.snd ].size() ) { const auto &e = G[ cur.snd ][i]; if ( dist[e] <= dist[ cur.snd ] + 1 ) { continue; } dist[e] = dist[ cur.snd ] + 1; prev[e] = cur.snd; que.push( MP( dist[ cur.snd + 1 ], e ) ); } } if ( dist[ N - 1 ] == INF ) { return VI(); } int cur = N - 1; VI res; while ( cur != 0 ) { res.PB( cur ); cur = prev[ cur ]; } res.PB( 0 ); reverse( ALL( res ) ); return res; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); string first, last; cin >> first >> last; if ( first == last ) { cout << 0 << endl << first << endl << last << endl; return 0; } int n; cin >> n; VS words; words.PB( first ); REP( i, 0, n ) { string tmp; cin >> tmp; words.PB( tmp ); } words.PB( last ); const int N = words.size(); VVI G( N, VI() ); REP( i, 0, N ) { REP( j, 0, N ) { if ( able( words[i], words[j] ) ) { G[i].PB( j ); } } } VI res = solve( G ); if ( res.size() == 0 ) { cout << -1 << endl; } else { cout << res.size() - 2 << endl; REP( i, 0, res.size() ) { cout << words[ res[i] ] << endl; } } return 0; }