本文介绍: 我们可以先从头变换5次,再从尾变换5次,然后对两组dis进行拼接。这样就把6^10降成了6^5*2。结果只过了87.5的数据(qaq)
显然,我们可以用BFS解决,具体实现与八数码类似:
下面是代码:
#include<bits/stdc++.h>
using namespace std;
#define N 3000000
string a,b;
int hh,dis[N],cnt;
struct node{
string u,v;
}bian[7];
map<string,int> mp;
string huan[N];
queue<int> q;
int bfs(string a,string b){
mp[a]=1;
huan[++cnt]=a;
dis[cnt]=0;
q.push(cnt);
while(!q.empty()){
int tmp=q.front();
q.pop();
if(dis[tmp]==10) return 0;
string now=huan[tmp];
for(int i=1;i<=hh;i++){
for(int j=0;j<now.length();){
string nxt=now;
int pos=now.find(bian[i].u,j);
if(pos<0&&pos>=now.length()) break;
j=pos+1;
nxt.erase(pos,bian[i].u.length());
nxt.insert(pos,bian[i].v);
if(mp.find(nxt)!=mp.end()) continue;
if(nxt.length()>20) continue;
dis[++cnt]=dis[tmp]+1;
mp[nxt]=cnt;
huan[cnt]=nxt;
q.push(cnt);
if(nxt==b) return dis[cnt];
}
}
}
return 0;
}
int main(){
cin>>a>>b;
while(cin>>bian[++hh].u>>bian[hh].v) ;
int u=bfs(a,b);
if(!u) cout<<"NO ANSWER!";
else cout<<u;
}
结果只过了87.5的数据(qaq)
实际上,这题虽然说只有6种变换法则,但是如果给的字符串恶心一点(比如适用同一法则的pos位置有很多,那么它的复杂度铁定远大于6^10,于是我们可以优化一下:
我们可以先从头变换5次,再从尾变换5次,然后对两组dis进行拼接。这样就把6^10降成了6^5*2。
下面为AC代码:
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
string a,b;
int hh,disA[N],cnt,disB[N];
struct node{
string u,v;
}bian[7];
map<string,int> mp;
string huan[N];
queue<int> q;
int bfs(string a,string b,int y,int dis[]){
while(!q.empty()) q.pop();
mp[a]=++cnt;
huan[cnt]=a;
dis[cnt]=0;
q.push(cnt);
while(!q.empty()){
int tmp=q.front();
q.pop();
if(dis[tmp]==5) return 0;
string now=huan[tmp];
for(int i=1;i<=hh;i++){
for(int j=0;j<now.length();){
string nxt=now;
if(y==1){
int pos=now.find(bian[i].u,j);
if(pos<0&&pos>=now.length()) break;
j=pos+1;
nxt.erase(pos,bian[i].u.length());
nxt.insert(pos,bian[i].v);}
if(y==0){
int pos=now.find(bian[i].v,j);
if(pos<0&&pos>=now.length()) break;
j=pos+1;
nxt.erase(pos,bian[i].v.length());
nxt.insert(pos,bian[i].u);}
if(nxt.length()>20) continue;
if(mp.find(nxt)!=mp.end()&&dis[mp[nxt]]!=-1) continue;
if(mp.find(nxt)==mp.end()){
dis[++cnt]=dis[tmp]+1;
mp[nxt]=cnt;
huan[cnt]=nxt;
q.push(cnt);}
else{
dis[mp[nxt]]=dis[tmp]+1;
q.push(mp[nxt]);
}
}
}
}
return 0;
}
int main(){
cin>>a>>b;
while(cin>>bian[++hh].u>>bian[hh].v) ;
memset(disA,-1,sizeof(disA));
memset(disB,-1,sizeof(disB));
bfs(a,b,1,disA);
bfs(b,a,0,disB);
int min1=11;
for(int i=1;i<=cnt;i++){
if(disA[i]!=-1&&disB[i]!=-1)
min1=min(min1,disA[i]+disB[i]);
}
if(min1>10) cout<<"NO ANSWER!";
else cout<<min1;
}
原文地址:https://blog.csdn.net/cocoack/article/details/136023872
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_66887.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。