2013年8月7日

UVa 1262 - Password

#include <cstdio>
#include <string>
#include <set>
#include <vector>
using namespace std;

set<string> all;
vector<char> alpha[5];

void find(int c, string pw) {
  if (c == 5) {
    all.insert(pw);
    return;
  }
  for (int i = 0; i < alpha[c].size(); i++) {
    find(c + 1, pw + alpha[c][i]);
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int K;
    scanf("%d", &K);
    char g1[9][9], g2[9][9];
    bool ok[9][199] = {};
    for (int r = 0; r < 6; r++) {
      scanf("%s", g1[r]);
    }
    for (int c = 0; c < 5; c++) {
      for (int r = 0; r < 6; r++) {
        ok[c][g1[r][c]] = true;
      }
    }
    for (int r = 0; r < 6; r++) {
      scanf("%s", g2[r]);
    }
    for (int c = 0; c < 5; c++) {
      alpha[c].clear();
      for (int r = 0; r < 6; r++) {
        if (ok[c][g2[r][c]]) {
          alpha[c].push_back(g2[r][c]);
        }
      }
    }
    all.clear();
    find(0, "");
    if (K > all.size()) {
      puts("NO");
      continue;
    }
    vector<string> ans(all.begin(), all.end());
    puts(ans[K - 1].c_str());
  }
  return 0;
}
Better one
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

vector<char> alpha[5];
bool solved;
int K, now;

void find(int c, string pw) {
  if (solved) {
    return;
  }
  if (c == 5) {
    now++;
    if (now == K) {
      puts(pw.c_str());
      solved = true;
    }
    return;
  }
  for (int i = 0; i < alpha[c].size(); i++) {
    find(c + 1, pw + alpha[c][i]);
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &K);
    char g1[9][9], g2[9][9];
    bool ok[9][199] = {};
    for (int r = 0; r < 6; r++) {
      scanf("%s", g1[r]);
    }
    for (int c = 0; c < 5; c++) {
      for (int r = 0; r < 6; r++) {
        ok[c][g1[r][c]] = true;
      }
    }
    for (int r = 0; r < 6; r++) {
      scanf("%s", g2[r]);
    }
    for (int c = 0; c < 5; c++) {
      set<char> temp;
      for (int r = 0; r < 6; r++) {
        if (ok[c][g2[r][c]]) {
          temp.insert(g2[r][c]);
        }
      }
      alpha[c] = vector<char>(temp.begin(), temp.end());
    }
    now = 0;
    solved = false;
    find(0, "");
    if (!solved) {
      puts("NO");
    }
  }
  return 0;
}

沒有留言:

張貼留言