Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-19

PKU 3803 -- Repeated Substitution with Sed

| 17:32 | PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj のブックマークコメント

やるだけ。


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

using namespace std;

set<string> memo;
string p[10], q[10];
string target;
int n, sol;

void search(string cur, int c)
{
  if(cur == target) {
    if(sol > c) sol = c;
    return;
  }
  if(c >= sol || cur.size() >= target.size()) return;
  if(memo.find(cur) != memo.end()) return;
  memo.insert(cur);
  for(int i=0, x=0, y=0; i<n; ++i, x=0, y=0) {
    string next = "";
    while(x < cur.size() && (x = cur.find(p[i], x)) != string::npos) {
      next += cur.substr(y, x-y) + q[i];
      y = x += p[i].size();
    }
    next += cur.substr(y);
    search(next, c+1);
  }
}

int main()
{
  while(scanf("%d", &n), n) {
    memo.clear();
    for(int i=0; i<n; ++i) {
      char a[12], b[12];
      scanf("%s%s", a, b);
      p[i] = a; q[i] = b;
    }
    char s[12], t[12];
    scanf("%s%s", s, t);
    target = t;
    sol = 100;
    search(s, 0);
    printf("%d\n", sol==100 ? -1 : sol);
  }
  return 0;
}
 |