#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 510;
int n;
string word[N];
// 如果两个队列共用st数组,那么两个队列永远不会碰头
// 因为在入队时我们会continue掉st为true的元素
// 而st为true时可能是另一个队列遍历掉的元素
unordered_map<string,bool> state, rstate;
unordered_map<string,int> d, rd;
int bfs(queue<string> &q, unordered_map<string,int> &dist,
unordered_map<string,int> &rdist,
unordered_map<string,bool> &st)
{
auto cur = q.front(); q.pop();
for(int i = 0; i < cur.size(); i ++ )
{
for(int j = 0; j < 26; j ++ )
{
string t = cur;
t[i] = 'a' + j;
if(st[t])
{
q.push(t);
dist[t] = dist[cur] + 1;
st[t] = false;
if(rdist[t]) return dist[t] + rdist[t] - 1;
}
}
}
return 0; // not found
}
int double_direction_bfs(string start, string goal)
{
if(start == goal) return 1;
queue<string> q, rq;
q.push(start);
rq.push(goal);
d[start] = 1;
rd[goal] = 1;
state[start] = false;
rstate[goal] = false;
// 每次只执行一个队列的bfs,优先执行队列中元素少的
while(q.size() && rq.size())
{
int r;
if(q.size() < rq.size()) r = bfs(q, d, rd, state);
else r = bfs(rq, rd, d, rstate);
if(r) return r;
}
return 0;
}
int main()
{
cin >> n;
for(int i = 0; i < n + 2; i ++ )
{
cin >> word[i];
state[word[i]] = true;
rstate[word[i]] = true;
}
cout << double_direction_bfs(word[0], word[1]) << endl;
return 0;
}
标签:return,int,双端,st,bfs,start,接龙,字符串,size
From: https://www.cnblogs.com/ALaterStart/p/18517431