80分求调
查看原帖
80分求调
1277996
mc2djwh楼主2024/9/28 20:59

第三个点wa了

#include <bits/stdc++.h>
using namespace std;
struct node{
	string str;
	int sp;
};
int main(){
	string a,b;
	cin>>a>>b;
	queue<node> q;
	set<string> vis;
	vector<pair<string,string>> rule;
	q.push({a,0});
	string tp1,tp2;
	while(cin>>tp1>>tp2){
		rule.push_back({tp1,tp2});
	}
	vis.insert(a);
	while(!q.empty()){
		node tmp=q.front();
		q.pop();
		vis.insert(tmp.str);
		if(tmp.sp>10){
			cout<<"NO ANSWER!";
			return 0;
		}
		if(tmp.str==b){
			cout<<tmp.sp;
			return 0;
		}
		for(pair<string, string> &r:rule){
			size_t zt=0;
			while((zt=tmp.str.find(r.first,zt))!=string::npos){
				string new_str=tmp.str.substr(0,zt)+r.second+tmp.str.substr(zt+r.first.size());
				if(!vis.count(new_str)){
					vis.insert(new_str);
					q.push({new_str,tmp.sp+1});
				}
				zt++;
			}
		}
	}
	return 0;
}
2024/9/28 20:59
加载中...