首页 > 其他 > 详细

uva 10981 - String Morphing(记忆化+离散)

时间:2014-05-06 21:14:17      阅读:440      评论:0      收藏:0      [点我收藏+]

题目链接:uva 10981 - String Morphing


题目大意:给出一个规则,表示由两个字符可以变成一个字符(题目中的表),然后给出一个字符串A,问如何同过规则变换得到B串,输出过程。


解题思路:记忆化搜索,每次枚举当前串可以变换的位置,然后记录下来,用map映射设,有个剪枝就是找到B串就可以结束搜索了。然后在从B串回溯输出答案。


#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <map>

using namespace std;
map<string, string> v;
string s, e;

inline char cat (char a, char b) {
	if (a == ‘a‘) {
		if (b == ‘c‘) return ‘a‘;
		return ‘b‘;
	} else if (a == ‘b‘) {
		return ‘c‘ - b + ‘a‘;
	} else {
		if (b == ‘a‘) return ‘a‘;
		return ‘c‘;
	}
}

bool dfs(string c) {

	int len = c.length();

	if (len == 1)
		return c == e;

	for (int i = 1; i < len; i++) {
		string tmp = "";
		for (int j = 0; j < i-1; j++)
			tmp = tmp + c[j];
		tmp = tmp + cat(c[i-1], c[i]);
		for (int j = i + 1; j < len; j++)
			tmp = tmp + c[j];

		if (v.count(tmp))
			continue;

		v[tmp] = c;
		if (dfs(tmp))
			return true;
	}
	return false;
}

void put(string c) {
	if (c != s)
		put(v[c]);
	cout << c << endl;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		cin >> s >> e;

		v.clear();

		if (dfs(s))
			put(e);
		else
			printf("None exist!\n");

		if (cas)
			printf("\n");
	}
	return 0;
}


uva 10981 - String Morphing(记忆化+离散),布布扣,bubuko.com

uva 10981 - String Morphing(记忆化+离散)

原文:http://blog.csdn.net/keshuai19940722/article/details/25096641

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!