- 取石子
单词S的烦恼题解!!!!!gzjun c++o11
- 2025-8-2 12:57:49 @
#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;
// 存储当前状态:当前的S和H
struct State {
string s;
string h;
State(string s_, string h_) : s(s_), h(h_) {}
};
// 为State结构体实现哈希函数,用于unordered_set
struct StateHash {
size_t operator()(const State& state) const {
return hash<string>()(state.s) ^ (hash<string>()(state.h) << 1);
}
};
// 为State结构体实现相等比较,用于unordered_set
struct StateEqual {
bool operator()(const State& a, const State& b) const {
return a.s == b.s && a.h == b.h;
}
};
bool canTransform(string S, string T, string H) {
// 边界情况处理
if (S == T) return true;
// 如果S长度小于T,不可能变换成功
if (S.length() < T.length()) return false;
// 如果目标T为空,只要移除S所有字符即可
if (T.empty()) return true;
// BFS队列和已访问集合
queue<State> q;
unordered_set<State, StateHash, StateEqual> visited;
// 初始化队列
q.push(State(S, H));
visited.insert(State(S, H));
while (!q.empty()) {
State current = q.front();
q.pop();
// 如果当前S的长度小于T,无法继续操作
if (current.s.length() < T.length()) continue;
// 操作1:将首字母移到H前面
string newS1 = current.s.substr(1); // 移除首字母后的S
string newH1 = current.s[0] + current.h; // 首字母移到H前面
if (newS1 == T) return true;
State next1(newS1, newH1);
if (visited.find(next1) == visited.end()) {
q.push(next1);
visited.insert(next1);
}
// 操作2:将尾字母移到H前面
string newS2 = current.s.substr(0, current.s.size() - 1); // 移除尾字母后的S
string newH2 = current.s.back() + current.h; // 尾字母移到H前面
if (newS2 == T) return true;
State next2(newS2, newH2);
if (visited.find(next2) == visited.end()) {
q.push(next2);
visited.insert(next2);
}
}
// 遍历所有可能状态后仍未找到目标
return false;
}
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
string S, T, H;
cin >> S >> T >> H;
if (canTransform(S, T, H)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
0 条评论
目前还没有评论...
信息
- ID
- 116
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 56
- 已通过
- 9
- 上传者