NOIP 2002 字串变换

题目描述
已知有两个字串A $，B$，B及一组字串变换的规则（至多6个规则）：
A1$ -> B1$
A2$ -> B2$
规则的含义为：在 A $中的子串A1$中的子串A1可以变换为B1 $、A2$、A2可以变换为B2$…

例如：A ${＝}^{\prime }abc{d}^{\prime }\hspace{1em}B$＝′abcd′ B＝’xyz’
变换规则为：
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
则此时，A $可以经过一系列的变换变为B$可以经过一系列的变换变为B，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得A $变换为B$变换为B。

• 输入
  一组测试数据，每组输入的第一行输入两个字符串A $和B$和B。
  接下来若干行输入变换规则：
  A$ B$
  A1$ B1$
  A2$ B2$ |-> 变换规则
  … … /
  所有字符串长度的上限为 20。
• 输出
  对于每组输入数据，若在10步（包含10步）以内能将A $变换为B$变换为B，则输出最少的变换步数，否则输出"NO ANSWER!"。
  样例输入

abcd xyz
abc xu
ud y
y yz

样例输出

3

bfs搜索，将所有变换存储，找到替换规则符合进行替换，并记录当前变换次数。
这里给出java的AC代码给大家参考

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashMap<String, ArrayList<String>> hm = new HashMap<>();
		String beg = sc.next();
		String end = sc.next();
		HashSet<String> use = new HashSet<>();
		while (sc.hasNext()) {
			String a = sc.next();
			String b = sc.next();

			ArrayList<String> al = hm.get(a);
			if (al != null) {
				al.add(b);
			} else {
				ArrayList<String> te = new ArrayList<>();
				te.add(b);
				hm.put(a, te);
			}
		}

		Set<String> hs = hm.keySet();
		Queue<String> q = new LinkedList<>();
		q.add(beg);
		use.add(beg);
		int ci = 0;
		int next = 0;
		int now = 1;
		boolean flag = false;
		while (!q.isEmpty()) {
			String s = q.poll();
			now--;
			if (s.equals(end)) {
				flag = true;
				break;
			}
			for (String str : hs) {
				for (int i = 0; i < s.length(); i++) {
					if (s.charAt(i) == str.charAt(0)) {
						boolean test = true;
						for (int j = 0; j < str.length(); j++) {
							if (i+j>=s.length()||s.charAt(i + j) != str.charAt(j)) {
								test = false;
							}
						}
						if (test) {
							ArrayList<String> re = hm.get(str);
							for (String string : re) {
								String temp = s.substring(0, i) + string + s.substring(i + str.length(), s.length());
								if(!use.contains(temp)) {
									q.add(temp);
									use.add(temp);
									next++;
								}
							}
						}
					}
				}
			}
			if (now <= 0) {
				now = next;
				ci++;
				if (ci > 10) {
					break;
				}
				next = 0;
			}
		}
		if (flag) {
			System.out.print(ci);
		} else {
			System.out.print("NO ANSWER!");
		}

	}
}