首页 > 代码库 > UVA 10941 - Words adjustment(BFS+字符串处理)
UVA 10941 - Words adjustment(BFS+字符串处理)
UVA 10941 - Words adjustment
题目链接
题意:给定两个字符串,在给定一些单词集合,问能否两个单词后面各添加一些单词,使得两个单词变成相同,问添加单词最少几次,单词要来自单词集合
思路:广搜,记录状态为两个字符串之间差的字符,利用set和string去乱搞。。即可
代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <queue> #include <algorithm> #include <set> using namespace std; int t; set<string> s, vis; string x, y; void init() { cin >> x >> y; string tmp; int q; cin >> q; s.clear(); while (q--) { cin >> tmp; s.insert(tmp); } } struct State { string str; int val; State() {} State (string str, int val) { this->str = str; this->val = val; } }; int solve() { queue<State> Q; if (x.length() > y.length()) Q.push(State(x.substr(y.length()), 0)); else Q.push(State(y.substr(x.length()), 0)); vis.clear(); vis.insert(Q.front().str); while (!Q.empty()) { State u = Q.front(); Q.pop(); if (u.str == "") return u.val; set<string>::iterator now = s.lower_bound(u.str); for (set<string>::iterator it = now; it != s.end() && it->substr(0, u.str.length()) == u.str; it++) { string tmp = it->substr(u.str.length()); if (vis.find(tmp) == vis.end()) { vis.insert(tmp); Q.push(State(tmp, u.val + 1)); } } for (int i = u.str.length(); i > 0; i--) { set<string>::iterator it = s.find(u.str.substr(0, i)); if (it != s.end()) { string tmp = u.str.substr(it->length()); if (vis.find(tmp) == vis.end()) { vis.insert(tmp); Q.push(State(tmp, u.val + 1)); } } } } return -1; } int main() { scanf("%d", &t); while (t--) { init(); cout << solve() << endl; } return 0; }
UVA 10941 - Words adjustment(BFS+字符串处理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。