\color{Red}{字串变换—双向广搜模型}
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
思路
双向广搜需要双方都每次搜一层,这样才能搜到最优解,因为每次如果只拓展一个点,可能未必是最优解,到另外一层搜索可能步数比没有搜到的点更多。 (不难理解)
这道题我们双向广搜的时候,明显哪个方向搜索,代码都是类似的,因此可以把搜索写成一个代码,然后就可以复用了。
而需要判断字符串的部分,显然需要更多考虑,我们是通过for
循环遍历以 i
开头的字串,故需要进行如果长度不够变换的剪枝。
这里可以使用 startWith()
优化一些多次使用subString
的代码,方便梳理逻辑。
JAVA
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static int N = 6, n;
static String[] a = new String[N];
static String[] b = new String[N];
static Scanner sc = new Scanner(System.in);
static int extend(LinkedList<String> qa, HashMap<String, Integer> da, HashMap<String, Integer> db, String[] a, String[] b) {
int d = da.get(qa.peek());
while (!qa.isEmpty() && da.get(qa.peek()) == d) {
String t = qa.pop();
for (int i = 0; i < t.length(); i++) {
for (int j = 0; j < n; j++) {
if (t.substring(i).length() < a[j].length()) continue;
if (t.startsWith(a[j], i)) {
String state = t.substring(0, i) + b[j] + t.substring(i + a[j].length());
if (db.containsKey(state)) return db.get(state) + da.get(t) + 1;
if (da.containsKey(state)) continue;
da.put(state, da.get(t) + 1);
qa.add(state);
}
}
}
}
return 11;
}
private static int bfs(String A, String B) {
if (A.equals(B)) return 0;
LinkedList<String> qa = new LinkedList<>();
LinkedList<String> qb = new LinkedList<>();
HashMap<String, Integer> da = new HashMap<>();
HashMap<String, Integer> db = new HashMap<>();
da.put(A, 0);
db.put(B, 0);
qa.add(A);
qb.add(B);
while (!qa.isEmpty() && !qb.isEmpty()) {
int t = 0;
if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);
else t = extend(qb, db, da, b, a);
if (t <= 10) return t;
}
return 11;
}
public static void main(String[] args) {
String A = sc.next();
String B = sc.next();
while (sc.hasNext()) {
a[n] = sc.next();
b[n++] = sc.next();
}
int ans = bfs(A, B);
if (ans <= 10) System.out.println(ans);
else System.out.println("NO ANSWER!");
}
}