2 条题解
-
0
#include<iostream> #include<bits/stdc++.h> using namespace std; int n; string A,B,C[2][7]; queue<string> q[2]; map<string,int> d[2]; int bfs(){ q[0].push(A); q[1].push(B); d[0][ A]=d[1][ B]=0; int step=10; while(step--){ //扩展层数 int u=(q[1].size()<q[0].size()); int m=q[ u].size(); while(m--){ //每层节点数 string f=q[ u].front(); q[ u].pop(); //父串 for(int i=0; i<n; i++) //枚举规则 for(int j=0; j<f.size(); j++) //枚举父串中的位置 if(f.substr(j,C[ u][i].size())==C[ u][i]){ string s=f.substr(0,j)+C[ u^1][i]+f.substr(j+C[ u][i].size()); if(d[ u].count(s)) continue; if(d[ u^1].count(s)) return d[ u][f]+d[u^1][s]+1; d[ u][s]=d[ u][f]+1; q[ u].push(s); } } } return 11; } int main(){ cin>>A>>B; while(cin>>C[0][n]>>C[1][n]) n++; int t=bfs(); t==11?printf("NO ANSWER!"):printf("%d",t); }#include <iostream> #include <queue> #include <unordered_map> using namespace std; const int N=7; int n; string A,B,a[N],b[N]; int extend(queue<string>&q, unordered_map<string,int>&da, unordered_map<string,int>&db, string a[], string b[]){ int m=q.size(); while(m--){ //每次扩展一层 auto f=q.front(); q.pop(); //父串出队 for(int i=0; i<n; i++) //枚举规则 for(int j=0; j<f.size(); j++) //枚举父串中的位置 if(f.substr(j,a[i].size())==a[i]){ string s=f.substr(0,j)+b[i]+f.substr(j+a[i].size()); if(da.count(s)) continue; if(db.count(s)) return da[ f]+db[ s]+1; da[s]=da[f]+1; //变换步数 q.push(s); //子串入队 } } return 11; } int bfs(){ if(A==B) return 0; queue<string> qa,qb; unordered_map<string,int> da,db; qa.push(A),qb.push(B); da[ A]=db[ B]=0; int step=10, t; while(step--){ if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b); else t=extend(qb,db,da,b,a); if(t<=10) return t; } return 11; } int main(){ cin>>A>>B; while(cin>>a[n]>>b[n]) n++; int t=bfs(); t==11?printf("NO ANSWER!"):printf("%d",t); } -
0
huangzheng
LV 6
@ 2025-10-8 16:55:23
#include<bits/stdc++.h> using namespace std; int n; string A,B,C[2][7]; queue<string> q[2]; map<string,int> d[2]; int bfs(){ q[0].push(A); q[1].push(B); d[0][ A]=d[1][ B]=0; int step=10; while(step--){ //扩展层数 int u=(q[1].size()<q[0].size()); int m=q[ u].size(); while(m--){ //每层节点数 string f=q[ u].front(); q[ u].pop(); //父串 for(int i=0; i<n; i++) //枚举规则 for(int j=0; j<f.size(); j++) //枚举父串中的位置 if(f.substr(j,C[ u][i].size())==C[ u][i]){ string s=f.substr(0,j)+C[ u^1][i]+f.substr(j+C[ u][i].size()); if(d[ u].count(s)) continue; if(d[ u^1].count(s)) return d[ u][f]+d[u^1][s]+1; d[ u][s]=d[ u][f]+1; q[ u].push(s); } } } return 11; } int main(){ cin>>A>>B; while(cin>>C[0][n]>>C[1][n]) n++; int t=bfs(); t==11?printf("NO ANSWER!"):printf("%d",t); }
#include <iostream> #include <queue> #include <unordered_map> using namespace std;
</p>const int N=7; int n; string A,B,a[N],b[N];
int extend(queue<string>&q, unordered_map<string,int>&da, unordered_map<string,int>&db, string a[], string b[]){ int m=q.size(); while(m--){ //每次扩展一层 auto f=q.front(); q.pop(); //父串出队 for(int i=0; i<n; i++) //枚举规则 for(int j=0; j<f.size(); j++) //枚举父串中的位置 if(f.substr(j,a[i].size())a[i]){ string s=f.substr(0,j)+b[i]+f.substr(j+a[i].size()); if(da.count(s)) continue; if(db.count(s)) return da[ f]+db[ s]+1; da[s]=da[f]+1; //变换步数 q.push(s); //子串入队 } } return 11; } int bfs(){ if(AB) return 0; queue<string> qa,qb; unordered_map<string,int> da,db; qa.push(A),qb.push(B); da[ A]=db[ B]=0;
int step=10, t; while(step--){ if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b); else t=extend(qb,db,da,b,a); if(t<=10) return t; } return 11; } int main(){ cin>>A>>B; while(cin>>a[n]>>b[n]) n++; int t=bfs(); t==11?printf("NO ANSWER!"):printf("%d",t); }
- 1