結果
問題 |
No.460 裏表ちわーわ
|
ユーザー |
|
提出日時 | 2016-12-10 23:45:36 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 573 ms |
コンパイル使用メモリ | 67,680 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-29 02:33:46 |
合計ジャッジ時間 | 4,061 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <iostream> #include <cstdio> #include <cstring> #include <cassert> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> using namespace std; typedef long long ll; const int INF = 114514; int H, W; int a[10][10], b[10][10]; int now(int i, int j){ int res = a[i][j]; for(int dy=-1;dy<=1;dy++)for(int dx=-1;dx<=1;dx++){ int ii = i + dy; int jj = j + dx; if(ii < 0 || ii >= H || jj < 0 || jj >= W)continue; res ^= b[ii][jj]; } return res; } int solve(int ym, int xm){ memset(b, 0, sizeof(b)); for(int i=0;i<H;i++)b[i][0] = (ym >> i) & 1; for(int j=0;j<W;j++)b[0][j] = (xm >> j) & 1; for(int i=1;i<H;i++){ for(int j=1;j<W;j++){ b[i][j] = now(i-1, j-1); } } int res = 0; for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(now(i, j) != 0) return INF; res += b[i][j]; } return res; } int main(){ cin >> H >> W; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ cin >> a[i][j]; } } int res = INF; for(int ym=0;ym<1<<H;ym++)for(int xm=0;xm<1<<W;xm++){ res = min(res, solve(ym, xm)); } if (res >= INF) { cout << "Impossible" << endl; } else { cout << res << endl; } return 0; }