ccbeginner

UVa Q10941

Feb 4th, 2020
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10941
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. bool check(string s1, string s2){
  6.     for(int i = 0; i < min(s1.size(), s2.size()); ++i){
  7.         if(s1[i] != s2[i])return 0;
  8.     }
  9.     return 1;
  10. }
  11.  
  12. string cut(string s1, string s2){
  13.     string tar = "";
  14.     if(s1.size() < s2.size())for(int i = s1.size(); i < s2.size(); ++i)tar += s2[i];
  15.     else for(int i = s2.size(); i < s1.size(); ++i)tar += s1[i];
  16.     return tar;
  17. }
  18.  
  19. string arr[1005];
  20.  
  21. int main(){
  22.     int t, n;
  23.     cin >> t;
  24.     while(t--){
  25.         string s1, s2, one;
  26.         cin >> s1 >> s2;
  27.         if(check(s1, s2))one = cut(s1, s2);
  28.         cin >> n;
  29.         for(int i = 0; i < n; ++i)cin >> arr[i];
  30.         map<string, int> vis;
  31.         deque<string> dq;
  32.         bool flag = 1;
  33.         if(one == ""){
  34.             cout << 0 << '\n';
  35.             flag = 0;
  36.         }else{
  37.             dq.emplace_back(one);
  38.             vis[one] = 0;
  39.         }
  40.         while(!dq.empty() && flag){
  41.             string tmd = dq.front();
  42.             dq.pop_front();
  43.             //cout << tmd << endl;
  44.             for(int i = 0; i < n && flag; ++i){
  45.                 if(check(arr[i], tmd)){
  46.                     string in = cut(tmd, arr[i]);
  47.                     if(in == ""){
  48.                         cout << vis[tmd]+1 << '\n';
  49.                         flag = 0;
  50.                     }else if(vis.find(in) == vis.end()){
  51.                         dq.emplace_back(in);
  52.                         vis[in] = vis[tmd]+1;
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.         if(flag)cout << -1 << '\n';
  58.     }
  59.     return 0;
  60. }
RAW Paste Data