Advertisement
Salman_CUET_18

counting cells in a blob

Nov 3rd, 2019
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pii pair<int, int>
  3. using namespace std;
  4. int fx[]= {+0,+0,+1,-1,-1,+1,-1,+1};
  5. int fy[]= {-1,+1,+0,+0,+1,+1,-1,-1};
  6. int  ans;
  7. string grid[26];
  8. bool vis[26][26];
  9. void bfs(int sx, int sy, int n, int m)
  10. {
  11.     int cnt = 1;
  12.     vis[sx][sy] = true;
  13.     queue<pii>q;
  14.     q.push(pii(sx, sy));
  15.     while(!q.empty())
  16.     {
  17.         pii top = q.front();
  18.         q.pop();
  19.         for(int i = 0; i < 8; i++)
  20.         {
  21.             int tx = top.first + fx[i];
  22.             int ty = top.second + fy[i];
  23.             if(tx >= 0 && tx < n && ty >= 0 && ty < m && vis[tx][ty] == false && grid[tx][ty] == '1')
  24.             {
  25.                 vis[tx][ty] = true;
  26.                 grid[tx][ty] = '0';
  27.                 q.push(pii(tx, ty));
  28.                 cnt++;
  29.             }
  30.         }
  31.     }
  32.     // cout << "cnt = " << cnt << endl;
  33.     ans = max(ans, cnt);
  34. }
  35. int main()
  36. {
  37.     int tc;
  38.     while(cin >> tc)
  39.     {
  40.         while(tc--)
  41.         {
  42.             int row = 0, col;
  43.             while(cin >> grid[row])
  44.             {
  45.                 col = grid[row].size();
  46.                 if(col == 0 )
  47.                     break;
  48.                 row++;
  49.             }
  50.             for(int i = 0; i < row; i++)
  51.             {
  52.                 for(int j = 0; j < col; j++)
  53.                 {
  54.                     if(grid[i][j] == '1')
  55.                         bfs(i, j, row, col);
  56.                 }
  57.             }
  58.             //cout << "len = " << len << endl;
  59.             cout << ans << endl;
  60.             if(tc)
  61.                 cout << endl;
  62.             memset(vis, 0, sizeof(vis));
  63.             for(int i = 0; i < row; i++)
  64.                 grid[i].clear();
  65.             ans = 0;
  66.         }
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement