結果

問題 No.460 裏表ちわーわ
ユーザー femto
提出日時 2016-12-11 15:05:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,248 bytes
コンパイル時間 1,864 ms
コンパイル使用メモリ 182,124 KB
実行使用メモリ 112,968 KB
最終ジャッジ日時 2024-11-29 03:32:56
合計ジャッジ時間 60,823 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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[0] = 0;

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

	while(q.size()) {
		ll cur = q.front();
		q.pop();

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

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

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

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