[NOIP2002]字串变换 T2 双向BFS-白红宇

[NOIP2002]字串变换 T2 双向BFS

阅读量：6830 次

发布时间：2019-06-26

本文共 1699 字，大约阅读时间需要 5 分钟。

题目描述

已知有两个字串 A

　　规则的含义为：在 A＄中的子串 A1

　　　　例如：A

　　变换规则为：

　　　　‘abc’-> ‘xu’

　　　　‘ud’-> ‘y’

　　　　‘y’-> ‘yz’

　　则此时，A

　　　‘abcd’-> ‘xud’-> ‘xy’-> ‘xyz’

　　共进行了三次变换，使得 A

输入

第一行为两个字符串，第二行至文件尾为变换规则

　　　　　... ... / 　　所有字符串长度的上限为 20。

输出

若在 10 步（包含 10步）以内能将 A

样例输入

abcd xyz abc xu ud y y yz

样例输出

(⊙o⊙)…

大概并不是很简单，我以为BFS就行...

但是.....

时间超限...

尴尬，GG

(⊙o⊙)…双向BFS弄完了就只剩下一点string的东西了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;const int N=11;struct Node{ string s; int d;};map
            
              m1,m2;queue
             
               q1,q2;string change[N][2],ss;Node s1,s2;int k,ans;int dbfs(){ while(!q1.empty()||!q2.empty()) { if(q1.front().d+q2.front().d>10) break; s1=q1.front(); int len=s1.s.length(); for(int i=0;i
              
               >s1.s>>s2.s; if(s1.s==s2.s){cout<<0<
               
                >change[k][0]>>change[k][1])k++; cout<
                
                 <

RE的，谁大概给我看看为什么...

#include
     
      #include
      
       #include
       #include
        
         #include
         
          using namespace std;typedef struct{
   string s;int d;}point;map
          
            m1,m2;queue
           
             q1,q2;string change[6][2],ss;point s1,s2;int k,ans; bool dbfs(){ while(!q1.empty()&&!q2.empty()){ if(q1.front().d+q2.front().d>10)return false; s1=q1.front(); int len=s1.s.length(); for(int i=0;i
            
             >s1.s>>s2.s; if(s1.s==s2.s){cout<<0<
             
              >change[k][0]>>change[k][1])k++; if(dbfs())cout<
              
               <