字符串骚操作
str.repalce( int s,int len,string str )
将起点为s，长度为len的字符串替换成str
str.insert( int s,string str )
起点为s，插入str
划重点，这题要是用insert一首凉凉。因为删除操作后下表会改变，insert个鬼哦
#include <bits/stdc++.h> using namespace std; typedef pair<string,int> pii; set<string> se; string ss1[10]; string ss2[10]; string A,B; int n; bool match( const string& s1,const int num,vector<string>& ve ){ int len1 = s1.length(); int len2 = ss1[num].length(); string& s2 = ss1[num]; for(int i = 0;i <= len1 - len2;i++ ){ bool flag = true; for( int j = 0;j < len2;j++ ){ if( s1[i+j] != s2[j] ){ flag = false; break; } } if( flag ){ string str = s1; str.replace( i,len2,ss2[num] ); ve.push_back( str ); } } if( ve.size() ) return true; return false; } queue<pii> que; int bfs( ){ que.push( pii(A,0 ) ); while( que.size() ){ pii x = que.front(); if( x.second >= 11 ) return -1; if( x.first == B ){ return x.second; } que.pop(); string str = x.first; for( int i = 1;i <= n;i++ ){ vector<string> ve; if( match( str,i,ve ) ){ for( int i = 0;i < ve.size();i++ ){ if( se.find( ve[i] ) ==se.end() ){ se.insert( ve[i] ); que.push( pii( ve[i],x.second+1 ) ); } } } } } return -1; } int main() { string x,y; cin >> A >> B; int i= 0; while( cin >>x >> y ){ ss1[++i] = x; ss2[i] = y; } n = i; se.insert( A ); int re = bfs(); if(re != -1){ printf("%d",re); }else{ printf("NO ANSWER!"); } return 0; }
