P1032 字串变换

题目描述

已知有两个字串 A,B 及一组字串变换的规则（至多 6 个规则），形如：

• A1​→B1​。
• A2​→B2​。

规则的含义为：在 A 中的子串 A1​ 可以变换为 B1​，A2​ 可以变换为 B2​ ⋯。

例如：A=abcd，B＝xyz，

变换规则为：

• abc→xu，ud→y，y→yz。

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

• abcd→xud→xy→xyz。

共进行了 3 次变换，使得 A 变换为 B。

输入格式

第一行有两个字符串 A,B。

接下来若干行，每行有两个字符串 Ai​,Bi​，表示一条变换规则。

输出格式

若在 10 步（包含 10 步）以内能将 A 变换为 B，则输出最少的变换步数；否则输出 NO ANSWER!。

输入输出样例

输入

abcd xyz
abc xu
ud y
y yz

输出

3

一道普通的搜索

for循环枚举每个变换规则，进行变化，判断终点，中途记录步数，如果步数大于10，也视为无解，输出NO ANSWER!如果队列为空了，那依旧是无解，输出NO ANSWER!如果找到了终点，那么就输出步数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b,A[7],B[7];
map<string,int> mp;
queue<string> q;
int ans=1;
void bfs(){
	q.push(a);
	while(!q.empty()){
		string t=q.front();
		q.pop();
		int mps=mp[t];
		if(mps>10){
			cout<<"NO ANSWER!";//步数大于十是无解
			return;
		}
		if(t==b){
			cout<<mp[t];
			return;
		}
		for(int i=1;i<ans;i++)
			for(int j=0;j<t.length();j++){
				if(t.substr(j,A[i].length())==A[i]){
					string o=t.substr(0,j)+B[i]+t.substr(j+A[i].length());
					if(mp[o]==0){//如果没找过，入队
						mp[o]=mps+1;
						q.push(o);
					}
				}
			}
	}
	cout<<"NO ANSWER!";//没找到也是无解
	return;
}
signed main(){
	cin>>a>>b;
	while(cin>>A[ans]>>B[ans])ans++;
	bfs();
}