fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <vector>
  5. #include <set>
  6. #include <climits>
  7. #include <algorithm>
  8. #include <map>
  9. using namespace std;
  10.  
  11. int n, m;
  12. int a[1001][1001];
  13.  
  14. bool visited[1001][1001];
  15. int dx[8] = { 1,1,1,-1,-1,-1,0,0 };
  16. int dy[8] = { 1,-1,0,1,-1,0,1,-1 };
  17.  
  18. const int MOD = (int)(1e9 + 7);
  19.  
  20. int i_max = 0, i_min = INT_MAX, j_max = 0, j_min = INT_MAX;
  21.  
  22. int cnt = 0;
  23.  
  24. void update(int i, int j) {
  25.     a[i][j] = 0;
  26.  
  27.     i_max = max(i_max, i);
  28.     i_min = min(i_min, i);
  29.  
  30.     j_max = max(j_max, j);
  31.     j_min = min(j_min, j);
  32. }
  33.  
  34. void dfs(int i, int j) {
  35.     update(i, j);
  36.  
  37.     cnt++;
  38.  
  39.     for (int k = 0;k < 8;k++) {
  40.         int ni = dx[k] + i;
  41.         int nj = dy[k] + j;
  42.  
  43.         if (ni >= 0 && ni < n && nj >= 0 && nj < m && a[ni][nj] == 1) {
  44.             dfs(ni, nj);
  45.         }
  46.     }
  47. }
  48.  
  49. int main() {
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.  
  53.     cin >> n >> m;
  54.  
  55.     int c = 0;
  56.  
  57.     vector<int> v;
  58.     for (int i = 0;i < n;i++) {
  59.         for (int j = 0;j < m;j++) {
  60.             cin >> a[i][j];
  61.         }
  62.     }
  63.  
  64.     for (int i = 0;i < n;i++) {
  65.         for (int j = 0;j < m;j++) {
  66.             if (a[i][j]) {
  67.                 i_max = 0, i_min = INT_MAX, j_max = 0, j_min = INT_MAX, cnt = 0;
  68.                 dfs(i, j);
  69.  
  70.                 int width = j_max - j_min + 1;
  71.                 int height = i_max - i_min + 1;
  72.  
  73.                 if (width * height == cnt) {
  74.                     c++;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     cout << c;
  80.     return 0;
  81. }
  82.  
  83.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uX1rUO
language:
C++ (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!