题目衔接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1091
题目大意:定义两个单词为doublet序列,当两个序列的长度相同,且只有一个字母不相同,给出一个单词库,求两个单词之间可以通过doublet序列转化的路径。
思路:开始想到了宽度优先搜索,以第一个单词为起点,依次访问与它距离为1的节点,递归进行直到找到目标单词,算法的时间复杂度上界是O(n*n),其中n 最大为25143,理论上是不会超时的,也有BFS的算法AC了,但是我的代码中用到了很多容器,主要是为了方便,所以超时了,下面是我的实现代码,同时贴出了一个比较巧妙的算法,该算法为转载他人的代码。
我的代码:
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <fstream>
#define maxn 25143+5
using namespace std;
vector<string> dictionary; //存放字典的容器
map<string,int> word_num; //单词和编号的匹配对
map<int,string> num_word; //编号和单词的匹配对
int parent[maxn]; //记录每个节点的父节点,用于记录路径
bool visited[maxn];
bool is_doublet(string str1,string str2)
{
int i=0;
for(int j=0;j<str1.length();j++)
{
if(str1[j] != str2[j])
i++;
if(i>=2)
return false;
}
if(i == 1)
return true;
else
return false;
}
void BFS(string first_str,string second_str)
{
map<string,int>::iterator str_map;
map<int,string>::iterator num_map;
int j = word_num[first_str];
parent[j] = -1; //将第一个单词的父节点设为-1
visited[j] = true;
queue<int> result;
result.push(j);
while(!result.empty())
{
int k = result.front();
result.pop();
if(num_word[k] == second_str)
break;
for(int i=0;i<dictionary.size();i++)
{
if(!visited[i] && is_doublet(num_word[k],dictionary[i]))
{
parent[i] = k;
result.push(i);
visited[i] = true;
}
}
}
stack<string> out_put;
out_put.push(second_str);
int m = word_num[second_str];
if(parent[m] == 0)
cout<<"No solution"<<endl<<endl;
else
{
while(parent[m] != -1)
{
m = parent[m];
out_put.push(num_word[m]);
}
while(!out_put.empty())
{
cout<<out_put.top()<<endl;
out_put.pop();
}
cout<<endl;
}
}
int main()
{
ifstream data;
data.open("data.txt");
string str;
int i=0;
while(getline(data,str) && str.length() !=0)
{
dictionary.push_back(str);
word_num.insert(make_pair(str,i));
num_word.insert(make_pair(i,str));
i++;
}
string first_str,second_str;
while( data>>first_str>>second_str)
{
memset(visited,false,sizeof(visited));
memset(parent,0,sizeof(parent));
if(first_str.length() != second_str.length())
cout<<"No solution"<<endl<<endl;
else
BFS(first_str,second_str);
}
}
转载的代码:
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <memory.h>
#include <queue>
using namespace std;
vector<string> dict;
map<string,int> pos;
int next[ 25200 ];
int main()
{
string wd;
while ( getline( cin, wd ), wd != "" )
{
pos[ wd ] = dict.size();
dict.push_back( wd );
}
int f = 0;
string s, t;
while ( cin >> s >> t )
{
if ( f++ ) puts("");
if ( pos.find( s ) == pos.end() )
{
puts("No solution.");
continue;
}
if ( pos.find( t ) == pos.end() )
{
puts("No solution.");
continue;
}
memset( next, -1, sizeof next );
int ids = pos[ s ];
int idt = pos[ t ];
next[ idt ] = -2;
queue< int > q;
q.push( idt );
while ( !q.empty() )
{
int u = q.front(); q.pop();
string s = dict[ u ];
for (int i=0; i<s.length(); i++)
for (int c='a'; c<='z'; c++)
{
string t = s;
t[ i ] = c;
if ( pos.find( t ) != pos.end() )
{
int v = pos[ t ];
if ( next[ v ] == -1 )
{
next[ v ] = u;
q.push( v );
}
}
}
}
if ( next[ids] == -1 ) puts("No solution.");
else
{
for (int i=ids; i!=-2; i=next[i]) cout << dict[ i ] << endl;
}
}
return 0;
}