SRM400 Div2 Hard

1000

上１行と左１列を全通り試す。
個人的にはMidより簡単な気がする。

int H, W;

char rev(char c)
{
  return c == '*' ? '.' : '*';
}

void turn(vector<string> &s, int i, int j)
{
  const int di[] = {-1, -1, -1,  0, 0,  0, +1, +1, +1};
  const int dj[] = {-1,  0, +1, -1, 0, +1, -1,  0, +1};
  for (int d = 0; d < 9; ++d) {
    int ni = i + di[d];
    int nj = j + dj[d];
    if (ni < 0 || nj < 0) continue;
    if (H <= ni || W <= nj) continue;
    s[ni][nj] = rev(s[ni][nj]);
  }
  return ;
}

const int inf = 1 << 29;

int f(vector<string> s)
{
  int cnt = 0;

  for (int i = 0; i < (int)H; ++i) cout << s[i] << endl; cout << endl;

  for (int i = 1; i < (int)H; ++i) {
    for (int j = 1; j < (int)W; ++j) {
      if (s[i - 1][j - 1] == '.') {
        turn(s, i, j);
        ++cnt;
      }
    }
  } 

  if (count(s.begin(), s.end(), string(s[0].size(), '*')) != (int)s.size()) {
    return inf;
  }
  return cnt;
}

class LightedPanels {
public:
  int minTouch(vector <string> B)
  {
    int mn = inf;

    H = B.size();
    W = B[0].size();

    const vector<string> tmp = B;

    for (int a = 0; a < (1 << H); ++a) {
      for (int b = 0; b < (1 << W); ++b) {
        int cnt = 0;
        B = tmp;

        for (int i = 0; i < (int)H; ++i) {
          if (a & (1 << i)) {
            turn(B, i, 0);
            ++cnt;
          }
        }
        for (int j = 1; j < (int)W; ++j) {
          if (b & (1 << j)) {
            turn(B, 0, j);
            ++cnt;
          }
        }
        mn = min(mn, f(B) + cnt);
      }
    }

    return mn == inf ? -1 : mn;
  }
};