bingxuan9112

2020 sprout pretest

Jan 13th, 2020
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.09 KB | None | 0 0
  1. //   __________________
  2. //  | ________________ |
  3. //  ||          ____  ||
  4. //  ||   /\    |      ||
  5. //  ||  /__\   |      ||
  6. //  || /    \  |____  ||
  7. //  ||________________||
  8. //  |__________________|
  9. //  \###################\
  10. //   \###################\
  11. //    \        ____       \
  12. //     \_______\___\_______\
  13. // An AC a day keeps the doctor away.
  14.  
  15. #pragma g++ optimize("Ofast")
  16. #pragma loop_opt(on)
  17. #include <bits/stdc++.h>
  18. #include <bits/extc++.h>
  19. #ifdef local
  20. #define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
  21. #else
  22. #define debug(x) ((void)0)
  23. #endif // local
  24. #define all(v) begin(v),end(v)
  25. #define siz(v) (ll(v.size()))
  26. #define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
  27. #define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
  28. #define pb emplace_back
  29. #define ff first
  30. #define ss second
  31. #define mem(v,x) memset(v,x,sizeof v)
  32.  
  33. using namespace std;
  34. using namespace __gnu_pbds;
  35. typedef int64_t ll;
  36. typedef long double ld;
  37. typedef pair<ll,ll> pll;
  38. typedef pair<ld,ld> pld;
  39. template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
  40. template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
  41. template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  42. constexpr ld PI = acos(-1), eps = 1e-5;
  43. constexpr ll N = 55, INF = 1e18, MOD = 998244353, K = 32, inf = 1e9;
  44. constexpr inline ll cdiv(ll x, ll m) { return x/m + (x<0 ^ m>0) && (x%m); } // ceiling divide
  45. //constexpr ll modpow(ll e,ll p,ll m=MOD) {ll r=1; for(;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r;}
  46.  
  47. int n,m,a,b,S[N][N],T[N][N],ans[N][N];
  48. void sol() {
  49.     cin >> n >> m;
  50.     for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> S[i][j];
  51.     cin >> a >> b;
  52.     for(int i = 0; i < a; i++) for(int j = 0; j < b; j++) cin >> T[i][j];
  53.     for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) ans[i][j] = 0;
  54.     for(int i = 0; i+a <= n; i++) for(int j = 0; j+b <= m; j++) if(!ans[i][j]){
  55.         ans[i][j] = 1;
  56.         for(int x = 0; x < a; x++) for(int y = 0; y < b; y++) if(T[x][y] != S[i+x][j+y]) ans[i][j] = 0;
  57.     }
  58.     for(int i = 0; i+b <= n; i++) for(int j = 0; j+a <= m; j++) if(!ans[i][j]){
  59.         ans[i][j] = 1;
  60.         for(int x = 0; x < b; x++) for(int y = 0; y < a; y++) if(T[y][x] != S[i+x][j+y]) ans[i][j] = 0;
  61.     }
  62.     for(int i = 0; i+a <= n; i++) for(int j = 0; j+b <= m; j++) if(!ans[i][j]){
  63.         ans[i][j] = 1;
  64.         for(int x = 0; x < a; x++) for(int y = 0; y < b; y++) if(T[x][b-1-y] != S[i+x][j+y]) ans[i][j] = 0;
  65.     }
  66.     for(int i = 0; i+b <= n; i++) for(int j = 0; j+a <= m; j++) if(!ans[i][j]){
  67.         ans[i][j] = 1;
  68.         for(int x = 0; x < b; x++) for(int y = 0; y < a; y++) if(T[a-1-y][x] != S[i+x][j+y]) ans[i][j] = 0;
  69.     }
  70.     //cout<<"===\n";
  71.     //for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cout << ans[i][j] << " \n"[j==m-1];
  72.     int res=0;
  73.     for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) res += ans[i][j];
  74.     cout<<res<<'\n';
  75. }
  76. signed main() {
  77.     ios_base::sync_with_stdio(0), cin.tie(0);
  78.     int t;
  79.     cin >> t;
  80.     while(t--) sol();
  81. }
Advertisement
Add Comment
Please, Sign In to add comment