AOJ 1296 - Repeated Substitution with Sed

問題概要

n個のαとβの組が与えられ、これは文字列の中にαがあればβに変換する。文字列を変換する際には左から優先して全てのαをβに変換しなければならない。文字列γから文字列δへ変換するための最小手数を求めよ。もし不可能な場合は-1を出力する。

制約

• n ≤ 10
• 1 ≤ |α_i| < |β_i| ≤ 10
• 1 ≤ |γ_i| < |δ_i| ≤ 10

解法

現在の文字列を状態に持ち、bfsをする。
変換の部分に注意が必要。

コード

#include <bits/stdc++.h>
  
using namespace std;
  
struct State{
  string s;
  int d;
};
  
int N,size[10];
string a[10],b[10],src,dst,str;
  
int solve(){
  queue<State> Q;
  Q.push((State){src,0});
  set<string> visited;
  visited.insert(src);
  
  while(!Q.empty()){
    State now = Q.front(); Q.pop();
    string s = now.s;
    if(s == dst) return now.d;
      
    for(int i = 0 ; i < N ; i++){
      string next;
      for(int j = 0 ; j < (int)s.size() ; j++){
        string sub = s.substr(j,size[i]);
        if(sub == a[i]){
          next += b[i];
          j += size[i]-1;
        }else{
          next += s[j];
        }
      }
      if(next.size() > dst.size()) continue;
      if(!visited.count(next)){
        visited.insert(next);
        Q.push((State){next,now.d+1});
      }
    }
  }
  return -1;
}
  
int main(){
  while(cin >> N, N){
    for(int i = 0 ; i < N ; i++){
      cin >> a[i] >> b[i];
      size[i] = a[i].size();
    }
    cin >> src >> dst;
    cout << solve() << endl;
  }
  return 0;
}