2013年8月21日

UVa 872 - Ordering

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


vector<char> alpha;
bool con[128][128], found;

void find(vector<char> & use, int * cnt) {
  if (use.size() == alpha.size()) {
    for (int i = 0; i < use.size(); i++) {
      printf("%c%s", use[i], i == alpha.size() - 1 ? "\n" : " ");
    }
    found = true;
    return;
  }
  for (int i = 0; i < alpha.size(); i++) {
    if (!cnt[alpha[i]]) {
      cnt[alpha[i]] = -1;
      for (int j = 0; j < alpha.size(); j++) {
        cnt[alpha[j]] -= con[alpha[i]][alpha[j]];
      }
      use.PB(alpha[i]);
      find(use, cnt);
      use.pop_back();
      for (int j = 0; j < alpha.size(); j++) {
        cnt[alpha[j]] += con[alpha[i]][alpha[j]];
      }
      cnt[alpha[i]] = 0;
    }
  }
}

int main() {
  char s[999];
  int T;
  gets(s);
  sscanf(s, "%d", &T);
  while (T--) {
    gets(s);
    gets(s);
    istringstream ss1(s);
    alpha.clear();
    while (ss1 >> s) {
      alpha.PB(s[0]);
    }
    gets(s);
    istringstream ss2(s);
    int cnt[128] = {};
    memset(con, false, sizeof(con));
    while (ss2 >> s) {
      con[s[0]][s[2]] = true;
      cnt[s[2]]++;
    }
    vector<char> use;
    found = false;
    find(use, cnt);
    if (!found) {
      puts("NO");
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言