kmjp's blog

競技プログラミング参加記です

AtCoder ARC #011 : C - ダブレット

続いて3問目。ここらへんからちょっと骨のある問題に。
http://arc011.contest.atcoder.jp/tasks/arc011_3


最初と最後の単語、あと途中で利用できる単語一覧が与えられる。
単語を1回で1文字ずつ変化させて(利用できる単語だけ利用して)最後の単語にたどり着く。
その際の最短経路を求める問題。マジカルバナナだね。

単語は高々1000個なので、単語間で変換できるかどうかを先に求め、後はBFSで最後の単語にたどり着く最短経路を探せばよい。
1点注意点は、最初と最後の単語が一致する場合、いきなりゴールできる(1文字変えなくて良い)点。

本番、この最初と最後の単語が一致する場合の出力をミスってWA喰らった…。
テストケースにあったのに無視したのがまずかった。

char str[1005][32];
vector<int> edge[1005];
int N,L;
int vis[1005],dis[1005];

int cango(char* a, char* b) {
	int i,r=0;
	FOR(i,L) if(a[i]!=b[i]) r++;
	return (r==1);
}

void dfs(int cur) {
	int i,j;
	
	FOR(i,edge[cur].size()) {
		int tar=edge[cur][i];
		if(dis[tar]>dis[cur]+1) {
			dis[tar]=dis[cur]+1;
			vis[tar]=cur;
		}
	}
	
	FOR(i,edge[cur].size()) {
		int tar=edge[cur][i];
		if(vis[tar]==cur) dfs(tar);
	}
	return;
}


void solve() {
	int f,r,i,j,k,l;

	GETs(str[0]);
	GETs(str[1004]);
	N=GETi();
	FOR(i,N) GETs(str[i+1]);
	strcpy(str[N+1],str[1004]);
	
	if(strcmp(str[0],str[N+1])==0) {
		_P("0\n%s\n%s\n",str[0],str[0]);
		return;
	}
	
	L=strlen(str[0]);
	FOR(i,N+2) for(j=i+1;j<N+2;j++) {
		if(cango(str[i],str[j])) {
			edge[i].push_back(j);
			edge[j].push_back(i);
		}
	}
	
	FOR(i,1004) vis[i]=-1;
	FOR(i,1004) dis[i]=100000;
	dis[0]=0;
	
	dfs(0);
	
	if(dis[N+1]==100000) {
		_P("-1\n");
	}
	else {
		vector<int> q;
		i=N+1;
		while(i!=0) {
			q.push_back(i);
			i=vis[i];
		}
		_P("%d\n%s\n",q.size()-1,str[0]);
		for(i=q.size()-1;i>=0;i--) _P("%s\n",str[q[i]]);
	}
	
	return;
}

まとめ

テストケースはちゃんと確認しないとね。