Advertisement
YEZAELP

TOI12: key_graph

Dec 25th, 2020
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using pi = pair <int, int>;
  6. char ar1[1010], ar2[1010];
  7. int l1, l2;
  8.  
  9. bool key(string s){
  10.  
  11.     queue <pi> q;
  12.     vector < vector <bool>> visited(l1 + 2, vector <bool> (l2 + 2, false));
  13.     q.push({0, 0});
  14.  
  15.     while(q.size() > 0){
  16.  
  17.         int a1 = q.front().first;
  18.         int a2 = q.front().second;
  19.         q.pop();
  20.  
  21.         if(a1 == l1 and a2 == l2)
  22.             return true;
  23.         if(a1 + a2 >= s.size() or visited[a1][a2])
  24.             continue;
  25.         visited[a1][a2] = true;
  26.  
  27.         if(!visited[a1+1][a2] and (s[a1+a2] == ar1[a1] or a2 == l2 and s[a1+a2] == ar1[a1]) )
  28.             q.push({a1+1, a2});
  29.         if(!visited[a1][a2+1] and (s[a1+a2] == ar2[a2] or a1 == l1 and s[a1+a2] == ar2[a2]) )
  30.             q.push({a1, a2+1});
  31.     }
  32.  
  33.     return false;
  34. }
  35.  
  36. int main(){
  37.  
  38.     scanf("%s", ar1);
  39.     scanf("%s", ar2);
  40.     l1 = strlen(ar1);
  41.     l2 = strlen(ar2);
  42.  
  43.     int n;
  44.     scanf("%d", &n);
  45.  
  46.     while(n--){
  47.  
  48.         string s;
  49.         cin >> s;
  50.         if(key(s)) printf("Yes\n");
  51.         else printf("No\n");
  52.  
  53.     }
  54.  
  55.     return 0;
  56. }
  57.  
Advertisement
RAW Paste Data Copied
Advertisement