SRM505 Div1 Easy

300

こういう感じの問題って凄く苦戦するんだけど、何かコツとかないのかな。

const int H = 50 + 1;
const int W = 50 + 1;
char g[H][W];

void rec(int i, int j, int h, int w)
{
  g[i][j] = 'Y';

  for (int a = 0; a < (int)h; ++a) {
    for (int b = 0; b < (int)w; ++b) {
      int cnt = 0;
      if (g[i][j] == 'Y') ++cnt;
      if (g[a][b] == 'Y') ++cnt;
      if (g[i][b] == 'Y') ++cnt;
      if (g[a][j] == 'Y') ++cnt;
      if (cnt == 3) {
        if (g[a][b] != 'Y') rec(a, b, h, w);
        if (g[i][b] != 'Y') rec(i, b, h, w);
        if (g[a][j] != 'Y') rec(a, j, h, w);
      }
    }
  }

  return ;
}

class RectangleArea {
public:
  int minimumQueries(vector <string> K)
  {
    for (int i = 0; i < (int)K.size(); ++i) {
      for (int j = 0; j < (int)K[i].size(); ++j) {
        g[i][j] = K[i][j];
      }
    }
   
    for (int i = 0; i < (int)K.size(); ++i) {
      for (int j = 0; j < (int)K[i].size(); ++j) {
        if (K[i][j] == 'Y') {
          rec(i, j, K.size(), K[i].size());
        }
      }
    }

    int ret = 0;
    for (int i = 0; i < (int)K.size(); ++i) {
      for (int j = 0; j < (int)K[i].size(); ++j) {
        if (g[i][j] == 'N') {
          rec(i, j, K.size(), K[0].size());
          ++ret;
        }
      }
    }

    return ret;
  }
};