寬度優先搜尋 UVA 10150 Doublets

題目銜接：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;
}