Advertisement
Manh_LK

Connected Cells in a Grid

Apr 5th, 2020
1,167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. struct toaDo {
  4.     int x, y;
  5. };
  6. int X[8] = {0,-1,0,1,-1,-1,1,1};
  7. int Y[8] = {-1,0,1,0,-1,1,1,-1};
  8. int main()
  9. {
  10.     //freopen("input.txt", "r", stdin);
  11.     int n, m;
  12.     cin >> n >> m;
  13.     int A[11][11];
  14.     for (int i = 0; i < n; i++)
  15.     {
  16.         for (int j = 0; j < m; j++)
  17.         {
  18.             cin >> A[i][j];
  19.         }
  20.     }
  21.     toaDo QQ[100];
  22.     int front = -1, rear = -1, res=0;
  23.     for (int i = 0; i < n; i++)
  24.     {
  25.         for (int j = 0; j < m; j++)
  26.         {
  27.             int count = 0;
  28.             if (A[i][j] == 1)
  29.             {
  30.                 struct toaDo D;
  31.                 D.x = i;
  32.                 D.y = j;
  33.                 rear = (rear + 1) % 100;
  34.                 QQ[rear] = D;
  35.                 count += 1;
  36.                 A[i][j] = 0;
  37.                 while (front != rear)
  38.                 {
  39.                     toaDo E;
  40.                     front = (front + 1) % 100;
  41.                     E.x = QQ[front].x;
  42.                     E.y = QQ[front].y;
  43.                     for (int direct = 0; direct < 8; direct++)
  44.                     {
  45.                         toaDo F;
  46.                         F.x = E.x + X[direct];
  47.                         F.y = E.y + Y[direct];
  48.                         if (F.x >= 0 && F.x < n && F.y >= 0 && F.y < m && A[F.x][F.y] == 1)
  49.                         {
  50.                             rear = (rear + 1) % 100;
  51.                             QQ[rear] = F;
  52.                             A[F.x][F.y] = 0;
  53.                             count += 1;
  54.                         }
  55.                     }
  56.                 }
  57.                 if (res < count) res = count;
  58.             }
  59.         }
  60.     }
  61.     cout << res;
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement