YEZAELP

TOI14: space_1

Dec 31st, 2020 (edited)
91
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 2e9;
  6. using pii = pair <int, int>;
  7. bool ar[1001][1001];
  8. int n, m;
  9.  
  10. int Height(int I, int J){
  11.     int cnt = 0;
  12.     for(int i=I;i<=n;i++){
  13.         if(!ar[i][J]) return cnt;
  14.         cnt ++;
  15.     }
  16.     return cnt;
  17. }
  18.  
  19. int Length(int I, int J){
  20.     int cnt = 0;
  21.     for(int j=J;j<=m;j++){
  22.         if(!ar[I][j]) return cnt;
  23.         cnt ++;
  24.     }
  25.     return cnt;
  26. }
  27.  
  28. void Square(int I, int J, int H, int L){
  29.     for(int i = I; i <= I+H-1; i++){
  30.         for(int j = J;j <= J+L-1; j++){
  31.             ar[i][j] = false;
  32.         }
  33.     }
  34. }
  35.  
  36. bool pst(int ui, int uj){
  37.     return ui >= 1 and ui <= n and uj >= 1 and uj <= m;
  38. }
  39.  
  40. bool Diamond(int I, int J, int H, int L){
  41.     queue <pii> q;
  42.     q.push({I, J});
  43.  
  44.     vector <int> mn(n+10, INF), mx(n+10, -INF);
  45.     int dx[] = {0, 0, 1, -1};
  46.     int dy[] = {1, -1, 0, 0};
  47.     while(q.size() > 0){
  48.         int ui, uj;
  49.         ui = q.front().first;
  50.         uj = q.front().second;
  51.         q.pop();
  52.         if(!ar[ui][uj])
  53.             continue;
  54.         ar[ui][uj] = false;
  55.         mn[ui] = min(mn[ui], uj);
  56.         mx[ui] = max(mx[ui], uj);
  57.         for(int d = 0; d < 4; d++){
  58.             int vi, vj;
  59.             vi = ui + dx[d];
  60.             vj = uj + dy[d];
  61.             if(pst(vi, vj) and ar[vi][vj]) {
  62.                 q.push({vi, vj});
  63.             }
  64.         }
  65.     }
  66.  
  67.     int idx = 1, cnt = 0, x = I + H/ 2 - 1;
  68.     for(int i = I; i <= I+H-1; i++){
  69.         if(mn[i] == INF or mn[i] == -INF) return false;
  70.         if(mx[i] - mn[i] != cnt) return false;
  71.         idx ++;
  72.         if(i <= x) cnt += 2;
  73.         else cnt -= 2;
  74.     }
  75.     return true;
  76. }
  77.  
  78. void filled(int I, int J){
  79.     queue <pii> q;
  80.     q.push({I, J});
  81.  
  82.     int dx[] = {0, 0, 1, -1};
  83.     int dy[] = {1, -1, 0, 0};
  84.     while(q.size() > 0){
  85.         int ui, uj;
  86.         ui = q.front().first;
  87.         uj = q.front().second;
  88.         q.pop();
  89.         if(!ar[ui][uj])
  90.             continue;
  91.         ar[ui][uj] = false;
  92.         for(int d = 0; d < 4; d++){
  93.             int vi, vj;
  94.             vi = ui + dx[d];
  95.             vj = uj + dy[d];
  96.             if(pst(vi, vj) and ar[vi][vj]) {
  97.                 q.push({vi, vj});
  98.             }
  99.         }
  100.     }
  101. }
  102.  
  103. void prt(){
  104.     for(int i=1;i<=n;i++){
  105.         for(int j=1;j<=m;j++){
  106.             if(ar[i][j]) printf("1");
  107.             else printf("0");
  108.         }
  109.         printf("\n");
  110.     }
  111.     cout << endl;
  112. }
  113.  
  114. int main(){
  115.  
  116.     scanf("%d%d", &m, &n);
  117.  
  118.     for(int i=1;i<=n;i++){
  119.         for(int j=1;j<=m;j++){
  120.             char x;
  121.             scanf(" %c", &x);
  122.             if(x == '1') ar[i][j] = true;
  123.         }
  124.     }
  125.  
  126.     int sq = 0, dm = 0, tri = 0;
  127.     for(int i=1;i<=n;i++){
  128.         for(int j=1;j<=m;j++){
  129.             if(!ar[i][j]) continue;
  130.             int H, L;
  131.             H = Height(i, j);
  132.             L = Length(i, j);
  133.             if(H == L) {
  134.                 Square(i, j, H, L);
  135.                 sq ++;
  136.             }
  137.             else if((H > 2 or L > 2) and Diamond(i, j, H, L)) {
  138.                 dm ++;
  139.             }
  140.             else {
  141.                 filled(i, j);
  142.                 tri ++;
  143.             }
  144.         }
  145.     }
  146.  
  147.     printf("%d %d %d\n", sq, dm, tri);
  148.  
  149.     return 0;
  150. }
  151.  
RAW Paste Data Copied