SRM411 Div2 Hard

900

塗りつぶす

view plainprint?

1. const int N = 200 + 10;  
2. int color[N][N];  
3.   
4. const int base = N / 2;  
5.   
6. bool vis[N][N];  
7. void rec(int i, int j)  
8. {  
9.   vis[i][j] = true;  
10.   const int di[] = {0, 0, -1, +1};  
11.   const int dj[] = {-1, +1, 0, 0};  
12.   for (int d = 0; d < 4; ++d) {  
13.     int ni = i + di[d];  
14.     int nj = j + dj[d];  
15.     if (ni < 0 || nj < 0) continue;  
16.     if (N <= ni || N <= nj) continue;  
17.     if (color[i][j] != color[ni][nj]) continue;  
18.     if (vis[ni][nj]) continue;  
19.     rec(ni, nj);  
20.   }  
21.   return ;  
22. }  
23.   
24. class HoleCakeCuts {  
25. public:  
26.   int cutTheCake(int cLength, int hLength, vector <int> hCuts, vector <int> vCuts)  
27.   {  
28.     int c = 0;  
29.   
30.     fill(&color[0][0], &color[N][0], -1);  
31.     for (int i = -cLength; i < +cLength; ++i) {  
32.       for (int j = -cLength; j < +cLength; ++j) {  
33.         color[i + base][j + base] = c;  
34.       }  
35.     }  
36.     ++c;  
37.   
38.     for (int i = -hLength; i < +hLength; ++i) {  
39.       for (int j = -hLength; j < +hLength; ++j) {  
40.         color[i + base][j + base] = -1;  
41.       }  
42.     }  
43.   
44.     hCuts.push_back(+cLength + 1);  
45.     hCuts.push_back(-cLength - 1);  
46.     vCuts.push_back(+cLength + 1);  
47.     vCuts.push_back(-cLength - 1);  
48.     sort(hCuts.begin(), hCuts.end());  
49.     sort(vCuts.begin(), vCuts.end());  
50.   
51.     for (int h = 0; h + 1 < hCuts.size(); ++h) {  
52.       for (int v = 0; v + 1 < vCuts.size(); ++v) {  
53.         bool flg = false;  
54.         for (int i = hCuts[h]; i < hCuts[h + 1] ; ++i) {  
55.           for (int j = vCuts[v]; j < vCuts[v + 1] ; ++j) {  
56.             if (0 <= color[i + base][j + base]) {  
57.               color[i + base][j + base] = c;  
58.               flg = true;  
59.             }  
60.           }  
61.         }  
62.         c += flg;  
63.       }  
64.     }  
65.   
66.     fill(&vis[0][0], &vis[N][0], false);  
67.     int ret = 0;  
68.     for (int i = 0; i < N; ++i) {  
69.       for (int j = 0; j < N; ++j) {  
70.         if (0 <= color[i][j] && !vis[i][j]) {  
71.           rec(i, j);  
72.           ++ret;  
73.         }  
74.       }  
75.     }  
76.     return ret;  
77.   }  
78. };  

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;
  }
};