torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Regular Contest #011, C : ダブレット

概要

ある単語について、文字を一文字置換する操作が許される。
与えられた辞書を使って、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;
}