結果

問題 No.13 囲みたい！
ユーザー data9824data9824
提出日時 2015-06-11 23:44:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 163 ms / 5,000 ms
コード長 1,812 bytes
コンパイル時間 601 ms
コンパイル使用メモリ 64,260 KB
実行使用メモリ 77,068 KB
最終ジャッジ日時 2023-08-03 13:54:55
合計ジャッジ時間 2,276 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 54 ms
67,668 KB
testcase_04 AC 23 ms
77,068 KB
testcase_05 AC 162 ms
67,908 KB
testcase_06 AC 24 ms
62,920 KB
testcase_07 AC 163 ms
69,220 KB
testcase_08 AC 143 ms
4,376 KB
testcase_09 AC 35 ms
4,380 KB
testcase_10 AC 9 ms
4,380 KB
testcase_11 AC 88 ms
4,380 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 21 ms
4,376 KB
testcase_14 AC 25 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

int w, h;
int vertexCount;
bool connected[10000][10000] = { false };
bool vertex[10000];
bool visited[10000];

int index(int x, int y) {
	return x + y * w;
}

bool scan(int start, int from) {
	if (visited[start]) {
		return true;
	}
	visited[start] = true;
	for (int i = 0; i < vertexCount; ++i) {
		if (i != from && connected[start][i]) {
			if (scan(i, start)) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> w >> h;
	vector<vector<int> > m(w, vector<int>(h));
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			cin >> m[x][y];
		}
	}
	vertexCount = w * h;
	bool found = false;
	for (int i = 1; i <= 1000 && !found; ++i) {
		fill(&vertex[0], &vertex[vertexCount - 1] + 1, false);
		fill(&visited[0], &visited[vertexCount - 1] + 1, false);
		for (int y = 0; y < h; ++y) {
			for (int x = 0; x < w; ++x) {
				if (m[x][y] == i) {
					vertex[index(x, y)] = true;
					if (x > 0 && m[x - 1][y] == i) {
						connected[index(x, y)][index(x - 1, y)] = true;
						connected[index(x - 1, y)][index(x, y)] = true;
					}
					if (x < w - 1 && m[x + 1][y] == i) {
						connected[index(x, y)][index(x + 1, y)] = true;
						connected[index(x + 1, y)][index(x, y)] = true;
					}
					if (y > 0 && m[x][y - 1] == i) {
						connected[index(x, y)][index(x, y - 1)] = true;
						connected[index(x, y - 1)][index(x, y)] = true;
					}
					if (y < h - 1 && m[x][y + 1] == i) {
						connected[index(x, y)][index(x, y + 1)] = true;
						connected[index(x, y + 1)][index(x, y)] = true;
					}
				}
			}
		}
		for (int start = 0; start < vertexCount && !found; ++start) {
			if (vertex[start] && !visited[start]) {
				found |= scan(start, -1);
			}
		}
	}
	cout << (found ? "possible" : "impossible") << endl;
	return 0;
}
0