[UVa] 10150 - Doublets

題目網址: http://goo.gl/ZXAbrU

題意:
(from luckycat)


解法: 建圖，BFS求最短路徑。

TAG: BFS

注意: 建圖要想一下

程式碼:

	/**
	* Tittle: 10150 - Doublets
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/10
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <queue>
	#include <map>
	#include <string>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 30000
	#define pb push_back
	typedef vector<int> VI;
	typedef queue<int> QI;
	typedef map<string,int> MSI;
	// declarations
	int wn;
	char dict[N][20];
	VI pool[20];
	MSI s2n[20];
	VI nbr[N];
	// functions
	bool doublet( int a, int b )
	{
	char *sa = dict[a];
	char *sb = dict[b];
	int sl = strlen(sa);
	int cnt = 0;
	FOR( i, 0, sl-1 ) if( sa[i]!=sb[i] )
	++cnt;
	return (cnt==1);
	}
	void buildgraph( void )
	{
	static int pn;
	static int u, v;
	FOR( k, 1, 16 ) {
	pn = pool[k].size();
	FOR( i, 0, pn-1 ) FOR( j, i+1, pn-1 ) {
	u = pool[k][i];
	v = pool[k][j];
	if( doublet(u,v) ) {
	nbr[u].pb(v);
	nbr[v].pb(u);
	}
	}
	}
	}
	void solve( char *s, char *t )
	{
	int sl = strlen(s);
	int tl = strlen(t);
	if( sl != tl ) {
	puts("No solution.");
	return;
	}
	int ps = s2n[sl][s];
	int pt = s2n[tl][t];
	QI que;
	bool vis[N];
	int pre[N];
	clr( vis, false );
	que.push(pt);
	vis[pt] = true;
	pre[pt] = -1;
	int u, v;
	while( !que.empty() ) {
	u = que.front(); que.pop();
	for( VI::iterator it=nbr[u].begin(); it!=nbr[u].end(); ++it ) {
	v = *it;
	if( vis[v] ) continue;
	vis[v] = true;
	pre[v] = u;
	que.push(v);
	}
	if( vis[ps] ) break;
	}
	if( vis[ps] ) {
	u = ps;
	while( u != -1 ) {
	puts(dict[u]);
	u = pre[u];
	}
	} else
	puts("No solution.");
	}
	// main function
	int main( void )
	{
	int sl;
	char s[20], t[20];
	// init
	FOR( i, 1, 16 ) {
	pool[i].clear();
	s2n[i].clear();
	}
	wn = 0;
	// input
	while( gets(dict[wn]) && dict[wn][0] ) {
	sl = strlen(dict[wn]);
	pool[sl].pb(wn);
	s2n[sl][dict[wn]] = wn;
	++wn;
	}
	buildgraph();
	// solve & output
	bool nl = false;
	while( scanf( "%s%s", s, t )==2 ) {
	if( nl ) putchar('\n');
	else nl = true;
	solve( s, t );
	}
	return 0;
	}

view raw 10150 - Doublets.cpp hosted with ❤ by GitHub