結果

問題 No.460 裏表ちわーわ
ユーザー femtofemto
提出日時 2016-12-11 15:05:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,248 bytes
コンパイル時間 1,755 ms
コンパイル使用メモリ 177,740 KB
実行使用メモリ 97,928 KB
最終ジャッジ日時 2023-08-19 11:22:03
合計ジャッジ時間 5,334 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 74 ms
5,844 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

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