Doublets

分析：如果把词典中的单词当作顶点，把doublet看作连接两个顶点的边，那么这个问题实际上是在一个无向图中搜索两个顶点间的最短路径，如果有的话。“最短路径”可能使人联想到复杂的Dijkstra或者更复杂的Floyd-Warshall算法，但在本题中，由于图的边没有权值，因此可以简单地使用以s为起点的广度优先搜索来找出到达点t的最短路径，如果有的话。<!--more-->

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <algorithm>
#include <cassert>

using namespace std;

bool doublet(const string & a, const string & b) {
  bool diff = false;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] != b[i]) {
      if (!diff)
        diff = true;
      else
        return false;
    }
  }
  assert(diff);
  return true;
}

typedef map<string, vector<string> > Graph;
typedef map<string, string> Pred;

vector<string> build_path(const Pred & pred, const string & t) {
  vector<string> path;
  path.push_back(t);
  Pred::const_iterator it;
  string d = t;
  while ((it = pred.find(d)) != pred.end()) {
    d = (*it).second;
    path.push_back(d);
  }
  reverse(path.begin(), path.end());
  return path;
}

bool search(const Graph & graph, const string & s, const string & t, vector<string> & path) {
  if (s.size() != t.size())
    return false;

  set<string> visited;
  Pred pred;
  deque<string> q;
  q.push_back(s);
  visited.insert(s);
  bool found = false;
  while (!q.empty() && !found) {
    string w = q.front();
    q.pop_front();
    const vector<string> & doublets = graph.at(w);
    for (int i = 0; i < doublets.size(); i++) {
      const string & d = doublets[i];
      if (d == t) {
        found = true;
        pred[t] = w;
        path = build_path(pred, t);
        break;
      }
      else if (!visited.count(d)) {
        visited.insert(d);
        q.push_back(d);
        pred[d] = w;
      }
    }
  }
  return found;
}

int main() {
  Graph graph;
  vector<vector<string> > dict(17);
  string line;
  while (getline(cin, line) && !line.empty()) {
    vector<string> & doublets = graph[line];
    vector<string> & words = dict[line.size()];
    for (int i = 0; i < words.size(); i++) {
      if (doublet(words[i], line)) {
        graph[words[i]].push_back(line);
        doublets.push_back(words[i]);
      }
    }
    words.push_back(line);
  }
  bool first = true;
  string s, t;
  while (cin >> s >> t) {
    if (first) {
      first = false;
    }
    else {
      cout << endl;
    }
    vector<string> path;
    if (search(graph, s, t, path)) {
      for (int i = 0; i < path.size(); i++) {
        cout << path[i] << endl;
      }
    }
    else {
      cout << "No solution." << endl;
    }
  }
  return 0;
}