AOJ 1296: 幅優先探索

問題

Repeated Substitution with Sed | Aizu Online Judge

n個のαとbの組が与えられる。1回の操作で文字列γの中のαを全てβに置き換えることができる。αとβを上手く使いながら、γをδに変換するのに必要な最小の操作回数を考える。

解法

幅優先探索。βはαより長く、δはγより長いことが保証されているので、何回か操作してδの長さを超えた時は、それ以上調べる必要はない。

コード

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                sc.close();
                break;
            }

            String[][] conv = new String[n][2];
            for (int i = 0; i < conv.length; i++) {
                conv[i][0] = sc.next();
                conv[i][1] = sc.next();
            }

            String before = sc.next();
            String after = sc.next();

            Deque<String> deque = new ArrayDeque<String>();
            deque.addLast(before);
            int depth = 0;
            boolean convertable = false;
         bfs: while (!deque.isEmpty()) {
                depth++;
                int size = deque.size();
                for (int q = 0; q < size; q++) {
                    String poll = deque.pollFirst();
                    for (int i = 0; i < conv.length; i++) {
                        String test = poll.replaceAll(conv[i][0], conv[i][1]);
                        if (test.equals(poll)) {
                            continue;
                        } else if (test.equals(after)) {
                            convertable = true;
                            break bfs;
                        } else if (test.length() <= after.length()) {
                            deque.addLast(test);
                        }
                    }
                }
            }
            if (convertable) {
                System.out.println(depth);
            } else {
                System.out.println(-1);
            }
        }
    }
}