链接：https://ac.nowcoder.com/acm/contest/38457/D
题目描述
给你一个包含 n 个单词的单词表。你需要将单词 s 以如下操作转换成 t。
每次改变 s 的一个字母。你需要保证改变后的 s=t 或在单词表中出现过。
询问最小操作次数并输出方案。如果不能将 s 变成 t，输出 -1。
你需要保证第一行的字符串是 s 且最后一行的字符串是 t。
示例1
输入
5 3
qwq
awa
qwa
pwq
abc
qaq aww
输出
3
qaq
qwq
qwa
awa
aww
示例2
输入
2 2
qw
wq
bb bb
输出
0
bb
bb
示例3
输入
3 2
bf
ab
fg
aa cd
输出
-1
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200200;
int n,m,idx;
string s[N];
int h[N],e[N],ne[N],pre[N],dist[N];
bool check(string s1,string s2)
{
int num=0;
for(int i=0;i<m;i++)
if(s1[i]!=s2[i]) num++;
if(num<=1) return true;
else return false;
}
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
queue<int> q;
memset(dist,0x3f3f3f3f,sizeof dist);
dist[n+2]=0;//从末尾往前找
q.push(n+2);
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+1)
{
dist[j]=dist[t]+1;
pre[j]=t;
q.push(j);
}
}
}
//到达不了s的话就输出-1
if(dist[n+1]==0x3f3f3f3f) return -1;
else return dist[n+1]-1;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n+2;i++)
cin>>s[i];
memset(h,-1,sizeof h);
for(int i=1;i<=n+2;i++)
for(int j=i+1;j<=n+2;j++)
{
//可以把每一个单词都看成一个点，
//两点之间能连边的条件为最多有一个字符不同
if(check(s[i],s[j]))
{
//无向图
add(i,j);
add(j,i);
}
}
int flag=bfs();
if(flag==-1) cout<<"-1"<<endl;
else
{
cout<<flag<<endl;
int idx=n+1;
while(pre[idx]!=n+2)
{
cout<<s[idx]<<endl;
idx=pre[idx];
}
cout<<s[idx]<<endl<<s[n+2]<<endl;
}
return 0;
}