2013年7月31日

UVa 10150 - Doublets

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#define MP make_pair
using namespace std;

struct Word {
  Word(string s, int index) : s(s), index(index) {}
  string s;
  int index;
};

typedef pair<Word, vector<string> > P;

bool ok(string & a, string & b) {
  int diff = 0;
  for (int i = 0; a[i]; i++) {
    diff += (a[i] != b[i]);
  }
  return diff <= 1;
}

vector<string> dic[99];
vector<int> con[99][29999];

int main() {
  char s[99];
  while (gets(s) && s[0]) {
    dic[string(s).length()].push_back(s);
  }

  for (int i = 1; i <= 16; i++) {
    for (int j = 0; j < dic[i].size(); j++) {
      for (int k = 0; k < dic[i].size(); k++) {
        if (j == k) {
          continue;
        }
        if (ok(dic[i][j], dic[i][k])) {
          con[i][j].push_back(k);
        }
      }
    }
  }

  bool first = true;

  while (gets(s)) {
    printf("%s", first ? "" : "\n");
    first = false;
    char t1[99], t2[99];
    sscanf(s, "%s%s", t1, t2);
    int i1, i2, len = string(t1).length();
    if (string(t2).length() != len) {
      puts("No solution.");
      continue;
    }
    for (int i = 0; i < dic[len].size(); i++) {
      if (dic[len][i] == t1) {
        i1 = i;
        break;
      }
    }
    Word now(t1, i1);
    string target(t2);
    queue<P> q;
    vector<string> path;
    path.push_back(t1);
    q.push(MP(now, path));
    bool find = false, visited[29999] = {};
    while (!q.empty()) {
      now = q.front().first;
      path = q.front().second;
      q.pop();
      if (now.s == target) {
        for (int i = 0; i < path.size(); i++) {
          puts(path[i].c_str());
        }
        find = true;
        break;
      }
      for (int i = 0; i < con[len][now.index].size(); i++) {
        int j = con[len][now.index][i];
        if (!visited[j]) {
          vector<string> newP = path;
          string newS = dic[len][j];
          newP.push_back(newS);
          q.push(MP(Word(newS, j), newP));
          visited[j] = true;
        }
      }
    }
    if (!find) {
      puts("No solution.");
    }
  }

  return 0;
}

沒有留言:

張貼留言