ペンキの色

0531.cpp

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};

int h, w;
int n;
int lx[1010], ly[1010], rx[1010], ry[1010];
vector<int> x, y;

bool d[2020][2020];

void dfs(int i, int j)
{
  if (i < 0 || j < 0 || h < i || w < j) return;
  if (d[i][j]) return;
  d[i][j] = true;

  for (int k = 0; k < 4; k++){
    dfs(i + dy[k], j + dx[k]);
  }
}

int main()
{
  while (cin >> h >> w, h){
    x = vector<int>();
    y = vector<int>();
    memset(d, false, sizeof(d));
    
    cin >> n;

    for (int i = 0; i < n; i++){
      cin >> lx[i] >> ly[i] >> rx[i] >> ry[i];
      x.push_back(lx[i]); x.push_back(rx[i]);
      y.push_back(ly[i]); y.push_back(ry[i]);
    }
    x.push_back(0); x.push_back(w);
    y.push_back(0); y.push_back(h);

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());

    for (int i = y.size() - 2; i >= 0; i--){
      for (int j = x.size() - 2; j >= 0; j--){
        bool f = false;
        for (int k = 0; k < n; k++){
          if (lx[k] <= x[j] && x[j + 1] <= rx[k] && 
              ly[k] <= y[i] && y[i + 1] <= ry[k]) f = true;
        }
        d[i][j] = f;
      }
    }

    h = y.size() - 2;
    w = x.size() - 2;

    int ans = 0;
    for (int i = 0; i < y.size() - 1; i++){
      for (int j = 0; j < x.size() - 1; j++){
        if (d[i][j]) continue;
        dfs(i, j);
        ans++;
      }
    }

    cout << ans << endl;
  }
}