SRM411 Div2 Hard

900

塗りつぶす

const int N = 200 + 10;
int color[N][N];

const int base = N / 2;

bool vis[N][N];
void rec(int i, int j)
{
  vis[i][j] = true;
  const int di[] = {0, 0, -1, +1};
  const int dj[] = {-1, +1, 0, 0};
  for (int d = 0; d < 4; ++d) {
    int ni = i + di[d];
    int nj = j + dj[d];
    if (ni < 0 || nj < 0) continue;
    if (N <= ni || N <= nj) continue;
    if (color[i][j] != color[ni][nj]) continue;
    if (vis[ni][nj]) continue;
    rec(ni, nj);
  }
  return ;
}

class HoleCakeCuts {
public:
  int cutTheCake(int cLength, int hLength, vector <int> hCuts, vector <int> vCuts)
  {
    int c = 0;

    fill(&color[0][0], &color[N][0], -1);
    for (int i = -cLength; i < +cLength; ++i) {
      for (int j = -cLength; j < +cLength; ++j) {
        color[i + base][j + base] = c;
      }
    }
    ++c;

    for (int i = -hLength; i < +hLength; ++i) {
      for (int j = -hLength; j < +hLength; ++j) {
        color[i + base][j + base] = -1;
      }
    }

    hCuts.push_back(+cLength + 1);
    hCuts.push_back(-cLength - 1);
    vCuts.push_back(+cLength + 1);
    vCuts.push_back(-cLength - 1);
    sort(hCuts.begin(), hCuts.end());
    sort(vCuts.begin(), vCuts.end());

    for (int h = 0; h + 1 < hCuts.size(); ++h) {
      for (int v = 0; v + 1 < vCuts.size(); ++v) {
        bool flg = false;
        for (int i = hCuts[h]; i < hCuts[h + 1] ; ++i) {
          for (int j = vCuts[v]; j < vCuts[v + 1] ; ++j) {
            if (0 <= color[i + base][j + base]) {
              color[i + base][j + base] = c;
              flg = true;
            }
          }
        }
        c += flg;
      }
    }

    fill(&vis[0][0], &vis[N][0], false);
    int ret = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (0 <= color[i][j] && !vis[i][j]) {
          rec(i, j);
          ++ret;
        }
      }
    }
    return ret;
  }
};