D

题意概括

根据我题目的理解，题目的要求为将最后一行输入的第一个字符转换为最后一行第二个字符，一次只能改动一个字符，而且改动后的字符必须是上方输入过的。

思路提供

我看到这一题的时候，首先想到的当然就是最短路了，毕竟这是求最短的转换问题嘛，而且我们注意到题目中给的转换条件是一次只能改一个字符（但看到样例2，发现也可以不转换字符，不然的话只能过95%），所以我主要的思路为在题目中所有出现的字符串中，在只有一个字符差距的字符串之间建立一条边标记长度为一，这样的话我们再在跑一边从n+1到n+2的最短路即可

详细代码

接下来就是大家最爱的代码了————

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int n,m,h;
string x[100005];
string ansl[100005];
struct node{//这里采用链式前向星存边，不会的话用邻接表或vector也是可以的
    int to,next,value;
}edgn[1000005];
int head[100005],tot,dist[100005],fa[1000005];
bool be[100005];
void add(int x,int y,int v){
    tot++;
    edgn[tot].to=y;
    edgn[tot].value=v;
    edgn[tot].next=head[x];
    head[x]=tot;
}
int dijkstra(){//跑一边堆优化版本的dijkstra
	for(int i=1;i<=n+2;i++){
		if(i==n+1) continue;
		dist[i]=1e9;
	}
	priority_queue<PII , vector<PII> , greater<PII> > heap;
	heap.push({0,n+1});
	while(!heap.empty()){
		PII t=heap.top();
		heap.pop();
		int ver=t.second,w=t.first;
		if(be[ver]) continue;
		be[ver]=1;
		for(int i=head[ver];i!=0;i=edgn[i].next){
			if(dist[edgn[i].to]>dist[ver]+edgn[i].value){
                fa[edgn[i].to]=ver;//与普通dijkstra不同的地方是要记录更新这个点的父节点，方便接下来输出
				dist[edgn[i].to]=dist[ver]+edgn[i].value;
				heap.push({dist[edgn[i].to],edgn[i].to});
			}
		}
	}
    return dist[n+2];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n+2;i++){
        cin>>x[i];
    }
    for(int i=1;i<=n+2;i++){
        for(int j=1;j<=n+2;j++){
            int cnt=0;
            for(int w=0;w<m;w++){
                if(x[i][w]!=x[j][w]) cnt++;//判断不同字符的个数
            }
            if(cnt<=1){//小于1的情况必须要考虑
                add(i,j,1);
                add(j,i,1);//无向图要反向建边
            }
        }
    }
    int ans=dijkstra(),now=n+2;
    if(ans==1e9){
        cout<<"-1";
        return 0;
    }
    cout<<ans-1<<endl;
    while(1){
        if(now==n+1){
            h++;
            ansl[h]=x[now];
            break;
        }
        h++;
        ansl[h]=x[now];
        now=fa[now];
    }//从下到上便利用过的边
    for(int i=h;i>=1;i--){//因为刚才是从下到上，所以要倒叙输出
        cout<<ansl[i]<<endl;
    }
    return 0;//愉快的结束啦！！！
}

后记

比赛的时候想到了，很遗憾时间不是很够

大家如果有哪里看不懂的欢迎私信我，安利一下我的洛谷主页