結果

問題 No.13 囲みたい！
コンテスト
ユーザー data9824
提出日時 2015-06-11 23:44:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 206 ms / 5,000 ms
コード長 1,812 bytes
コンパイル時間 555 ms
コンパイル使用メモリ 63,992 KB
実行使用メモリ 45,440 KB
最終ジャッジ日時 2024-10-13 10:44:20
合計ジャッジ時間 2,049 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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