結果

問題 No.460 裏表ちわーわ
ユーザー siman
提出日時 2021-11-25 17:05:45
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 1,741 bytes
コンパイル時間 1,774 ms
コンパイル使用メモリ 142,592 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 09:38:52
合計ジャッジ時間 4,650 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

const int DY[9] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int DX[9] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int M, N;

void flip(int y, int x, vector<vector<int>> &G) {
  for (int i = 0; i < 9; ++i) {
    int ny = y + DY[i];
    int nx = x + DX[i];
    if (ny < 0 || nx < 0 || M <= ny || N <= nx) continue;

    G[ny][nx] ^= 1;
  }
}

int f(vector<vector<int>> &G) {
  int cnt = 0;

  for (int y = 1; y < M; ++y) {
    for (int x = 1; x < N; ++x) {
      if (G[y - 1][x - 1] == 0) continue;

      flip(y, x, G);
      ++cnt;
    }
  }

  for (int y = 0; y < M; ++y) {
    for (int x = 0; x < N; ++x) {
      if (G[y][x] == 1) return -1;
    }
  }

  return cnt;
}

int main() {
  cin >> M >> N;

  vector<vector<int>> G(M, vector<int>(N));
  for (int y = 0; y < M; ++y) {
    for (int x = 0; x < N; ++x) {
      cin >> G[y][x];
    }
  }

  int ans = INT_MAX;

  for (int mask_y = 0; mask_y < (1 << M); ++mask_y) {
    for (int mask_x = 0; mask_x < (1 << N); ++mask_x) {
      vector<vector<int>> CG = G;
      int cnt = 0;

      for (int y = 0; y < M; ++y) {
        if (mask_y >> y & 1) {
          flip(y, 0, CG);
          ++cnt;
        }
      }

      for (int x = 0; x < N; ++x) {
        if (mask_x >> x & 1) {
          flip(0, x, CG);
          ++cnt;
        }
      }

      int v = f(CG);
      if (v != -1) {
        cnt += v;
        ans = min(ans, cnt);
      }
    }
  }

  if (ans == INT_MAX) {
    cout << "Impossible" << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}
0