結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー femto
提出日時 2016-12-11 15:02:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,230 bytes
コンパイル時間 1,887 ms
コンパイル使用メモリ 180,436 KB
実行使用メモリ 104,300 KB
最終ジャッジ日時 2024-11-29 03:31:53
合計ジャッジ時間 60,788 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int H, W;

ll f(ll k, int x, int y) {
	ll ret = 0;
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			int c = i * W + j;
			ret |= k & (1LL << c);
			if(x - 1 <= j && j <= x + 1 && y - 1 <= i && i <= y + 1) {
				ret ^= (1LL << c);
			}
		}
	}
	return ret;
}

void view(ll s) {
	for(int y = 0; y < H; y++) {
		for(int x = 0; x < W; x++) {
			cout << (s >> (y * W + x) & 1) << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> H >> W;
	ll s = 0;
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			ll a;
			cin >> a;
			s |= a << (i * W + j);
		}
	}

	if(s == 0) {
		cout << 0 << endl;
		return 0;
	}

	unordered_map<ll, int> m;
	m[s] = 0;

	queue<ll> q;
	q.push(s);

	while(q.size()) {
		s = q.front();
		q.pop();

		//view(s);
		int t = m[s];

		if(s == 0) {
			cout << t << endl;
			return 0;
		}

		for(int y = 0; y < H; y++) {
			for(int x = 0; x < W; x++) {
				ll ns = f(s, x, y);
				//view(ns);
				if(m.count(ns) == 0) {
					m[ns] = t + 1;
					q.push(ns);
				}
			}
		}
	}

	if(m.count(0)) {
		cout << m[0] << endl;
	}
	else {
		cout << "Impossible" << endl;
	}
}
0