2012年12月28日

UVa 124 - Following Orders


#include <cstdio>
#include <set>
#include <string>

bool c[26][26], first;
std::set<int> alpha;

void dfs(int i, int* count, std::string s) {
  if (i == alpha.size()) {
    puts(s.c_str());
    return;
  }
  int j, k;
  for (j = 0; j < 26; j++) {
    if (!count[j] && alpha.count(j)) {
      count[j] = -1;
      s.insert(s.end(), j + 'a');
      for (k = 1; k < 26; k++)
        if (c[j][k]) count[k]--;
      dfs(i + 1, count, s);
      count[j] = 0;
      for (k = 1; k < 26; k++)
        if (c[j][k]) count[k]++;
      s.erase(s.end() - 1);
    }
  }
}

int main() {
  char s[99];
  while (gets(s)) {
    if (first) puts("");
    first = 1;
    alpha.erase(alpha.begin(), alpha.end());
    int i, j, k, count[26] = {};
    for (i = 0; i < 26; i++)
      for (j = 0; j < 26; j++)
        c[i][j] = 0;
    for (i = 0; s[i]; i++)
      if (s[i] != ' ') alpha.insert(s[i] - 'a');
    gets(s);
    for (i = 2; ; i += 4) {
      c[s[i - 2] - 'a'][s[i] - 'a'] = 1;
      count[s[i] - 'a']++;
      if (!s[i + 1]) break;
    }
    dfs(0, count, "");
  }
  return 0;
}

沒有留言:

張貼留言