单词序列

题面

给出两个单词（开始单词和结束单词）以及一个词典。找出从开始单词转换到结束单词所需的最短转换序列。转换规则如下：每次只能改变一个字母；转换过程中出现的单词（除开始单词和结束单词外）必须存在于词典中。例如，开始单词为 hit，结束单词为 cog，词典为 hot, dog, dot, lot, log,那么一种可能的最短变换是 hit hot dot dog cog，所以返回的结果是序列的长度 5。注意：如果找不到这种变换，则输出 0；词典中所有单词的长度相同；所有的单词都由小写字母构成；开始单词和结束单词可以不在词典中。

输入
hit cog
hot dot dog lot log

输出
5

思路

AC 代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<map>

using namespace std;

int tt = 0;

string start, last;
queue<string> q;  //队列
unordered_map<string, int> dis;  //string 对应的距离

int bfs()
{
	q.push(start);

	dis[start] = 0;

	while (!q.empty())
	{
		string t = q.front();
		q.pop();

		if (t == last)return dis[last] ;

		string str = t;

		for(int i = 0; i < t.size();i++)
		{
			char d = 'a';
			for (d = 'a'; d <= 'z'; d++)
			{
				char c = t[i];
				t[i] = d;
				if (dis.count(t)&&!dis[t]) //在字典中并且是第一次出现
				{
					q.push(t); //入队
					dis[t] = dis[str] + 1; //更新
				}
				t[i] = c;
			}
		}

	}

	return dis[last];
}

int main()
{
	cin >> start >> last;

	cin.ignore(); // 忽略换行符

	string str;


	getline(cin, str);

	string a[1000];
	
	dis[last] = 0;


	for (int i = 0; i < str.size(); i++)
	{	
		char c = str[i];
		if (c == ' ')  tt++;
		if (c != ' ')a[tt] += c;
	}

	for (int i = 0; i <= tt; i++) dis[a[i]] = 0;
	
	cout << bfs()<<endl;

	return 0;
}