Submission #67858

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
int g[1005][1005];
int diff(string s1, string s2){
	int cnt=0;
	for(int i=0;i<s1.length();++i){
		if(s1[i]!=s2[i])++cnt;
	}
	if(cnt==1)return 1;
	return 0;
}
int main(){

	memset(g,0,sizeof(g));

	string first,last;
	cin>>first>>last;
	if(first==last){
		cout<<0<<endl;
		cout<<first<<endl;
		cout<<first<<endl;
		return 0;

	}
	int N;
	cin>>N;
	vector <string> in;
	in.push_back(first);
	for(int i=0;i<N;++i){
		string s;
		cin>>s;
		in.push_back(s);
	}
	in.push_back(last);


	for(int i=0;i<in.size();++i){
		for(int j=i+1;j<in.size();++j){
			if(diff(in[i],in[j])){
				g[i][j]=1;
				g[j][i]=1;
			}
		}
	}
	int sz=in.size();
	
	queue < pair<int, vector<int> > > q;
	vector <int> tmp;
	q.push(pair<int,vector<int> >(0,tmp));

	int len[in.size()];
	for(int i=0;i<sz;++i)len[i]=INT_MAX;
	len[0]=0;
	vector <int> result;
	while(!q.empty()){
		int pos=(q.front()).first;
		vector <int> path=(q.front()).second;
		if(pos==sz-1)result=path;
		q.pop();
		vector <int> nxt=path;
		nxt.push_back(pos);
		for(int j=0;j<sz;++j){
			if(g[pos][j]){
				if(len[j]>nxt.size()){
					q.push(pair<int,vector<int> >
						(j,nxt));
					len[j]=nxt.size();
				}
			}
		}
	}

	if(len[in.size()-1]==INT_MAX){
		cout<<-1<<endl;
		return 0;
	}

	cout<<result.size()-1<<endl;
	for(int i=0;i<result.size();++i){
		cout<<in[result[i]]<<endl;
	}
	cout<<last<<endl;
	cout<<endl;


}

Submission Info

Judge Result