P1032 [NOIP2002 提高组] 字串变换

题目描述

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

• 1A1?→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?，表示一条变换规则。

输出格式

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

输入输出样例

输入 #1复制

abcd xyz
abc xu
ud y
y yz

输出 #1复制

3

说明/提示

对于?100%100%?数据，保证所有字符串长度的上限为?2020。

【题目来源】

NOIP 2002 提高组第二题

解析：

使用双端队列可以极小的减少搜索范围：

注意逆向的时候是从后变到前的。

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include<cstring>

using namespace std;
//双端队列 +  map记录已走过的步数  
queue<string> q1,q2;
string A,B;
string a1[10],a2[10];
int n = 0;
int expand(queue<string>& q,map<string,int>& m1,map<string,int>& m2,string a1[],string a2[])
{
	string t = q.front();
	q.pop();
	
	for(int i = 0;i < t.size();i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(t.substr(i,a1[j].size()) == a1[j])
			{
					string s1 = t.substr(0,i) + a2[j] + t.substr(i+a1[j].size()); // 变成下一个字符 
					if(m1.count(s1)) continue;
					if(m2.count(s1))  return m1[t]+1+m2[s1];
					m1[s1] = m1[t]+1;
					q.push(s1);
			}
		}
	}
	return 11;
}
int bfs()
{
	map<string,int> m1,m2;
	q1.push(A),m1[A] = 0;
	q2.push(B),m2[B] = 0;
	while(q1.size() && q2.size()) // 有断层 
	{
		int t;// 每次扩展元素少的  
		if(q1.size() < q2.size()) t = expand(q1,m1,m2,a1,a2);
		else t = expand(q2,m2,m1,a2,a1);
		if(t  <= 10) return t; 
	}
	return 11;
}
int main()
{
	cin >> A >> B;
	while(cin >> a1[n] >> a2[n]) n++;
//	for(int i = 0;i < 3;i++)
//	{
//		cin >> a1[i] >> a2[i];
//	}
//	n = 3;
	if(A == B)
	{
		cout << "0";
		return 0;		
	}		
	int step = bfs();
	if(step > 10)
		cout <<"NO ANSWER!"<<endl;
	else{
		cout << step<<endl;
	} 
	return 0;
}