Advertisement
kokokozhina

615

Jan 2nd, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. vector<string> readPhoto()
  9. {
  10.     int n, m;
  11.     cin >> n >> m;
  12.     vector<string> result(n);
  13.     for(int i = 0; i < n; i++)
  14.         cin >> result[i];
  15.     return result;
  16. }
  17.  
  18.  
  19. vector<string> cut(vector<string> f)
  20. {
  21.     int minx = INT_MAX;
  22.     int maxx = INT_MIN;
  23.     int miny = INT_MAX;
  24.     int maxy = INT_MIN;
  25.     for(int i = 0; i < f.size(); i++)
  26.         for(int j = 0; j < f[0].length(); j++)
  27.         {
  28.             if (f[i][j] == '*')
  29.             {
  30.                 minx = min(minx, i);
  31.                 maxx = max(maxx, i);
  32.                 miny = min(miny, j);
  33.                 maxy = max(maxy, j);
  34.             }
  35.         }
  36.     if (minx <= maxx)
  37.     {
  38.         vector<string> result(maxx - minx + 1, string(maxy - miny + 1, '?'));
  39.         for(int i = 0; i < maxx - minx + 1; i++)
  40.             for(int j = 0; j < maxy - miny + 1; j++)
  41.                 result[i][j] = f[i + minx][j + miny];
  42.         return result;
  43.     }
  44.     else
  45.         return vector<string> ();
  46. }
  47.  
  48. vector<string> rotate(vector<string> f)
  49. {
  50.     if (f.empty())
  51.         return f;
  52.     vector<string> result(f[0].length(), string(f.size(), '?'));
  53.     for(int i = 0; i < f.size(); i++)
  54.         for(int j = 0; j < f[0].length(); j++)
  55.             result[f[0].length() - j - 1][i] = f[i][j]; //clockwise
  56.     return result;
  57. }
  58.  
  59. vector<string> canonise(vector<string> f)
  60. {
  61.     f = cut(f);
  62.     vector<string> result = f;
  63.     for(int i = 0; i < 3; i++)
  64.     {
  65.         f = rotate(f);
  66.         result = min(result, f);
  67.     }
  68.     return result;
  69. }
  70.  
  71.  
  72. int main()
  73. {
  74.     vector<string> a = readPhoto();
  75.     vector<string> b = readPhoto();
  76.  
  77.     if (canonise(a) == canonise(b))
  78.         cout << "YES\n";
  79.     else
  80.         cout << "NO\n";
  81.  
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement