P1032 字串变换

题目描述

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

A_1​ ->B_1​

A_2​ -> B_2

规则的含义为：在 A中的子串 A_1 可以变换为B_1，A_2 可以变换为 B_2 …。

例如：A='abcdabcd'BB＝'xyzxyz'

变换规则为：

‘abcabc’->‘xuxu’‘udud’->‘yy’‘yy’->‘yzyz’

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

‘abcdabcd’->‘xudxud’->‘xyxy’->‘xyzxyz’

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

输入格式：

输入格式如下：

AA BB

A_1 ​ B_1

A_2 ​ B_2​

... ... /

所有字符串长度的上限为20。

输出格式：

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

输入样例#1

abcd xyz
abc xu
ud y
y yz

输出样例#1

3

题目分析

这个题有几个要注意的地方，

1.要标记已经处理过的子串

2.要留心一个字符串中，有多处可以应用同一个规则的地方，应枚举完

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
using namespace std;
struct node {
	string s;
	int step;
	node(string t, int m) {
		s = t;
		step = m;
	}
};
map<string, int> mymap;//用来标记是否访问过
string a, b;
string p1[8];//记录规则i的初始串
string p2[8];//记录规则i原串变换成的串
int num = 0;//记录几种规则
int sum = 0;
void dfs() {
	//将初始串入队
	queue<node> myq;
	myq.push(node(a,0));

	while (!myq.empty()) {
		//出队
		string t = myq.front().s;
		int m = myq.front().step;
		myq.pop();
		//若以访问，则跳过
		if (mymap[t] == 1)
			continue;
		//将串标记为已访问
		mymap[t]++;
		//满足要求
		if (t == b) {
			sum = m;
			return;
		}
		//枚举所有的规则
		for (int i = 0; i < num; i++) {
			int num = 0;
			//查找串中所有可以应用规则i的地方，并应用规则i、入队
			for (int j = t.find(p1[i], num); j < t.size() && j != -1; num = j + p1[i].size()) {
				string tt = t;
				j = t.find(p1[i], num);
				if (j != -1) {
					tt.replace(j, p1[i].size(), p2[i]);
					myq.push(node(tt, m + 1));
				}
			}
		}
	}

}
int main(){
	//freopen("in.txt", "r", stdin);
	cin >> a >> b;
	while (cin >> p1[num] >> p2[num]) {
		num++;
	}
	dfs();
	if (sum == 0 || sum > 10)//不能变换和变换次数大于等于10
		cout << "NO ANSWER!" << endl;
	else
		cout << sum << endl;
	return 0;
}