fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 1e3 + 5;
  6. int m, n, k;
  7. int b[N][N]; 
  8. int dx[4] = {1, -1, 0, 0};
  9. int dy[4] = {0, 0, 1, -1};
  10. const int INF = 1e9 + 5;
  11.  
  12. void loang(int x, int y, int val) {
  13.     queue<pair<int, int>> q;
  14.     q.push({x, y});
  15.     b[x][y] = INF; 
  16.     while (!q.empty()) {
  17.         auto [cx, cy] = q.front(); q.pop();
  18.         for (int d = 0; d < 4; ++d) {
  19.             int nx = cx + dx[d];
  20.             int ny = cy + dy[d];
  21.             if (nx >= 0 && nx < m && ny >= 0 && ny < n && b[nx][ny] == val) {
  22.                 b[nx][ny] = INF; 
  23.                 q.push({nx, ny});
  24.             }
  25.         }
  26.     }
  27. }
  28.  
  29. int32_t main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(0);
  32.  
  33.     while (true) {
  34.         cin >> m >> n;
  35.         if (m == 0 && n == 0) break;
  36.  
  37.         cin >> k;
  38.         memset(b, 0, sizeof(b));
  39.  
  40.         for (int i = 1; i <= k; ++i) {
  41.             int x1, y1, x2, y2;
  42.             cin >> x1 >> y1 >> x2 >> y2;
  43.             for (int x = max(x1, 0ll); x < min(x2, m); ++x) {
  44.                 for (int y = max(y1, 0ll); y < min(y2, n); ++y) {
  45.                     b[x][y] += (1 << (i)); 
  46.                 }
  47.             }
  48.         }
  49.         int ans = 0;
  50.         for (int i = 0; i < m; ++i) {
  51.             for (int j = 0; j < n; ++j) {
  52.                 if (b[i][j] != INF && b[i][j] != 0) {
  53.                     ans++;
  54.                     loang(i, j, b[i][j]);
  55.                 }
  56.             }
  57.         }
  58.         cout << ans << "\n"; 
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 11404KB
comments (?)
stdin
copy 
3 5
3
1 1 3 2
4 0 2 3
4 0 5 1
6 6
2
2 0 5 3
3 1 4 2
0 0
stdout
copy 
1
2
https://ideone.com/n19LgA
language:
C++14 (gcc 8.3)
created:
277 days 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!