ccbeginner

UVa Q10949

Feb 10th, 2020
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. char maze[21][21];
  5.  
  6. void func(string &s){
  7.     s = "";
  8.     int n, x, y;
  9.     char c;
  10.     cin >> n >> x >> y;
  11.     for(int i = 0; i < n; ++i){
  12.         s += maze[x][y];
  13.         cin >> c;
  14.         if(c == 'N')--x;
  15.         else if(c == 'S')++x;
  16.         else if(c == 'W')--y;
  17.         else if(c == 'E')++y;
  18.     }
  19.     s += maze[x][y];
  20. }
  21.  
  22. vector<int> v[130];
  23. vector<int> ans;
  24.  
  25. int32_t main(){
  26.     int t,h,w,n;
  27.     string s1, s2;
  28.     cin >> t;
  29.     for(int k = 1; k <= t; ++k){
  30.         cin >> h >> w;
  31.         for(int i = 1; i <= h; ++i){
  32.             for(int j = 1; j <= w; ++j){
  33.                 cin >> maze[i][j];
  34.             }
  35.         }
  36.         func(s1);
  37.         func(s2);
  38.         //cout << s1 << endl << s2 << endl;
  39.         for(int i = 33; i <= 127; ++i)v[i].clear();
  40.         n = 0;
  41.         ans.clear();
  42.         for(int i = 0; i < s1.size(); ++i)v[s1[i]].emplace_back(i);
  43.         for(int i = 0; i < s2.size(); ++i){
  44.             int len = ans.size() - 1;
  45.             for(int j = v[s2[i]].size()-1; j >= 0; --j){
  46.                 for(; len >= 0; --len){
  47.                     if(ans[len] < v[s2[i]][j])break;
  48.                 }
  49.                 if(len+1 == ans.size())ans.emplace_back(v[s2[i]][j]);
  50.                 else ans[len+1] = v[s2[i]][j];
  51.             }
  52.         }
  53.         cout << "Case " << k << ": " << s1.size()-ans.size() << ' ' << s2.size()-ans.size() << '\n';
  54.     }
  55.     return 0;
  56. }
RAW Paste Data