SRM533 Div1 Medium

500
行と列を頂点にすると、オイラーパスの問題になる。
連結かどうか調べる必要があるのを最後まで忘れていた。

void dfs(int i, int j, vector<string> &B)
{
  B[i][j] = '.';
  for (int k = 0; k < (int)B.size(); ++k) {
    if (B[k][j] == '#') dfs(k, j, B);
  }
  for (int k = 0; k < (int)B[i].size(); ++k) {
    if (B[i][k] == '#') dfs(i, k, B);
  }
  return ;
}

class MagicBoard {
public:
  string ableToUnlock(vector <string> B)
  {
    const int h = B.size();
    const int w = B[0].size();

    vector<int> R[h];
    vector<int> C[w];

    for (int i = 0; i < (int)h; ++i) {
      for (int j = 0; j < (int)w; ++j) {
        if (B[i][j] == '#') {
          R[i].push_back(j);
          C[j].push_back(i);
        }
      }
    }    
    
    int r, c;
    r = c = 0;

    for (int i = 0; i < (int)w; ++i) {
      c += C[i].size() % 2;
    }
    for (int i = 0; i < (int)h; ++i) {
      r += R[i].size() % 2;
    }

    cout << r << ' ' << c << endl;

    if (r + c == 0 || (r + c == 2 && c)) ; else return "NO";

    for (int i = 0; i < (int)h; ++i) {
      for (int j = 0; j < (int)w; ++j) {
        if (B[i][j] == '#') {
          dfs(i, j, B);
          return count(B.begin(), B.end(), string(w, '.')) == B.size() ? "YES" : "NO";
        }
      }
    }

    return "@";
 }
};