2013年8月28日

UVa 843 - Crypt Kicker

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>
#define PB push_back
using namespace std;

vector<string> dic[17];
bool found;

void solve(int now, vector<string> & words, int * encode, bool * done) {
  if (found) {
    return;
  }
  if (now == words.size()) {
    found = true;
    for (int i = 0; i < words.size(); i++) {
      for (int j = 0; words[i][j]; j++) {
        putchar(encode[words[i][j] - 'a'] + 'a');
      }
      putchar(i == words.size() - 1 ? '\n' : ' ');
    }
    return;
  }
  int len = words[now].length();
  for (int i = 0; i < dic[len].size(); i++) {
    bool ok = true;
    vector<int> before, after;
    for (int j = 0; words[now][j] && ok; j++) {
      char c1 = words[now][j] - 'a', c2 = dic[len][i][j] - 'a';
      if (done[c2]) {
        ok = (encode[c1] == c2);
      } else {
        ok = (encode[c1] == -1);
        before.PB(c1);
        after.PB(c2);
      }
    }
    for (int j = 0; j < before.size() && ok; j++) {
      for (int k = j + 1; k < before.size() && ok; k++) {
        if (before[j] == before[k]) {
          ok = (after[j] == after[k]);
        } else {
          ok = (after[j] != after[k]);
        }
        if (after[j] == after[k]) {
          ok = (before[j] == before[k]);
        } else {
          ok = (before[j] != before[k]);
        }
      }
    }
    if (!ok) {
      continue;
    }
    for (int j = 0; j < before.size(); j++) {
      encode[before[j]] = after[j];
      done[after[j]] = true;
    }
    solve(now + 1, words, encode, done);
    for (int j = 0; j < before.size(); j++) {
      encode[before[j]] = -1;
      done[after[j]] = false;
    }
  }
}

int main() {
  char s[1111];
  gets(s);
  int n;
  sscanf(s, "%d", &n);
  while (n--) {
    gets(s);
    dic[strlen(s)].PB(s);
  }
  while (gets(s)) {
    istringstream ss(s);
    string voc;
    vector<string> words;
    while (ss >> voc) {
      words.PB(voc);
    }
    int encode[26];
    memset(encode, -1, sizeof(encode));
    bool done[26] = {};
    found = false;
    solve(0, words, encode, done);
    if (!found) {
      for (int i = 0; s[i]; i++) {
        putchar(s[i] == ' ' ? ' ' : '*');
      }
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言