Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.99 KB | None | 0 0
  1. //
  2. // Created by Savva Morev 2019
  3. //
  4.  
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #pragma GCC optimize("Ofast")
  7. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
  8. #pragma GCC optimize("unroll-loops")
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <cmath>
  13. #include <limits>
  14. #include <ctime>
  15. #include <cassert>
  16. #include <map>
  17. #include <set>
  18. #include <iostream>
  19. #include <string>
  20. #include <vector>
  21. #include <algorithm>
  22. #include <functional>
  23. #include <fstream>
  24. #include <sstream>
  25. #include <stack>
  26. #include <queue>
  27. #include <numeric>
  28. #include <iterator>
  29. #include <bitset>
  30. #include <unordered_map>
  31. #include <unordered_set>
  32.  
  33. using namespace std;
  34.  
  35. #define sz(c) ((int)c.size())
  36. #define pb push_back
  37. #define pf push_front
  38. #define fi first
  39. #define se second
  40. #define all(x) (x).begin(), (x).end()
  41. #define endl "\n"
  42. #define x first
  43. #define y second
  44.  
  45. typedef long double ld;
  46. typedef long long ll;
  47. typedef pair <int, int> pii;
  48.  
  49. const int N = int(1e6) + 111;
  50. const int INF = int(1e9) + 111;
  51. const ll LINF = ll(1e18) + 111;
  52. const ld EPS = 1e-7;
  53. const ld PI = 3.141592653589793238462643;
  54. const ll MOD = 1e9 + 7;
  55. const int M = int(1e6) + 111;
  56. const int P = int(1e6) + 3;
  57.  
  58. template<class T> void chmin(T& a, const T& b) { if (a > b) a = b; }
  59. template<class T> void chmax(T& a, const T& b) { if (a < b) a = b; }
  60.  
  61. template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
  62. template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
  63. template<class T> T abs(T a) { return a >= 0 ? a : -a; }
  64.  
  65. int n, m;
  66. vector <vector <char>> a;
  67. int _n, _m;
  68. vector <vector <char>> b;
  69.  
  70. bool check(int x, int y) {
  71.     for (int i = x; i < x + _n; i++) {
  72.         for (int j = y; j < y + _m; j++) {
  73.             if (b[i - x][j - y] != a[i][j])
  74.                 return 0;
  75.         }
  76.     }
  77.     return 1;
  78. }
  79. bool check() {
  80.     for (int i = 0; i < n; i++) {
  81.         for (int j = 0; j < m; j++) {
  82.             if (i + _n > n || j + _m > m) continue;
  83.             if (check(i, j)) {
  84.                 return 1;
  85.             }
  86.         }
  87.     }
  88.     return 0;
  89. }
  90. void rotate() {
  91.     vector <vector <char>> tmp(_m, vector <char> (_n));
  92.     for (int i = 0; i < _n; i++)
  93.         for (int j = 0; j < _m; j++) {
  94.             tmp[j][_n - 1 - i] = b[i][j];
  95.         }
  96.     b = tmp;
  97.     swap(_n, _m);
  98. }
  99. void print() {
  100.     for (int i = 0; i < _n; i++) {
  101.         for (int j = 0; j < _m; j++) {
  102.             cout << b[i][j] << " ";
  103.         }
  104.         cout << endl;
  105.     }
  106. }
  107. vector <vector<char>> cut(int x, int y, int _x, int _y) {
  108.     _n = _x - x + 1;
  109.     _m = _y - y + 1;
  110.     vector <vector<char>> tmp(_n, vector <char>(_m));
  111.     for (int i = x; i <= _x; i++) {
  112.         for (int j = y; j <= _y; j++) {
  113.             tmp[i - x][j - y] = b[i][j];
  114.         }
  115.     }
  116.     return tmp;
  117. }
  118. int main() {
  119.     ios::sync_with_stdio(0);
  120.     cin.tie(0);
  121.     //ifstream cin("levenshtein.in");
  122.     //ofstream cout("levenshtein.out");
  123.     cin >> n >> m;
  124.     a.resize(n, vector <char> (m));
  125.     bool f = 0;
  126.     for (int i = 0; i < n; i++) {
  127.         for (int j = 0; j < m; j++) {
  128.             cin >> a[i][j];
  129.             f |= (a[i][j] == '*');
  130.         }
  131.     }
  132.     cin >> _n >> _m;
  133.     b.resize(_n, vector <char> (_m));
  134.     int x, y;
  135.     int _x, _y;
  136.     x = y = _x = _y = -1;
  137.     for (int i = 0; i < _n; i++) {
  138.         for (int j = 0; j < _m; j++) {
  139.             cin >> b[i][j];
  140.             if (b[i][j] == '*') {
  141.                 if (x == -1) {
  142.                     x = _x = i;
  143.                     y = _y = j;
  144.                 }
  145.                 x = min(x, i);
  146.                 y = min(y, j);
  147.                 _x = max(_x, i);
  148.                 _y = max(_y, j);
  149.             }
  150.         }
  151.     }
  152.     if (x == -1) {
  153.         cout << (f ? "NO" : "YES");
  154.         return 0;
  155.     }
  156.     b = cut(x, y, _x, _y);
  157.     for (int it = 0; it < 4; it++) {
  158.         print();
  159.         if (check()) {
  160.             cout << "YES";
  161.             return 0;
  162.         }
  163.         rotate();
  164.     }
  165.     cout << "NO";
  166.  
  167.     return 0;
  168. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement