UVA 10941 - Words adjustment

题目链接

题意：给定两个字符串，在给定一些单词集合，问能否两个单词后面各添加一些单词，使得两个单词变成相同，问添加单词最少几次，单词要来自单词集合

思路：广搜，记录状态为两个字符串之间差的字符，利用set和string去乱搞。。即可

代码：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int t; set
         
           s, vis; string x, y; void init() { cin >> x >> y; string tmp; int q; cin >> q; s.clear(); while (q--) { cin >> tmp; s.insert(tmp); } } struct State { string str; int val; State() {} State (string str, int val) { this->str = str; this->val = val; } }; int solve() { queue
          
            Q; if (x.length() > y.length()) Q.push(State(x.substr(y.length()), 0)); else Q.push(State(y.substr(x.length()), 0)); vis.clear(); vis.insert(Q.front().str); while (!Q.empty()) { State u = Q.front(); Q.pop(); if (u.str == "") return u.val; set
           
            ::iterator now = s.lower_bound(u.str); for (set
            
             ::iterator it = now; it != s.end() && it->substr(0, u.str.length()) == u.str; it++) { string tmp = it->substr(u.str.length()); if (vis.find(tmp) == vis.end()) { vis.insert(tmp); Q.push(State(tmp, u.val + 1)); } } for (int i = u.str.length(); i > 0; i--) { set
             
              ::iterator it = s.find(u.str.substr(0, i)); if (it != s.end()) { string tmp = u.str.substr(it->length()); if (vis.find(tmp) == vis.end()) { vis.insert(tmp); Q.push(State(tmp, u.val + 1)); } } } } return -1; } int main() { scanf("%d", &t); while (t--) { init(); cout << solve() << endl; } return 0; }
             
            
           
          
         
        
       
      
     
    
   
  

?