続いて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; }
まとめ
テストケースはちゃんと確認しないとね。