結果

問題 No.13 囲みたい！
コンテスト
ユーザー pekempey
提出日時 2015-08-18 16:20:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,287 bytes
コンパイル時間 1,383 ms
コンパイル使用メモリ 161,832 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 10:46:52
合計ジャッジ時間 1,985 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;
const ll inf = 1e9;
const ll mod = 573;

struct UF {
	vector<int> parent, size;
	UF(int n) : parent(n), size(n, 1) {
		rep (i, n) parent[i] = i;
	}
	int root(int x) {
		if (x == parent[x]) return x;
		else return parent[x] = root(parent[x]);
	}
	void unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return;
		if (size[x] > size[y]) swap(x, y);
		size[x] += size[y];
		parent[y] = x;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
};

int H, W;
int G[100][100];

int main() {
	cin >> W >> H;
	rep (i, H) rep (j, W) cin >> G[i][j];

	UF uf(H * W);	

	int dy[] = {0, 1};
	int dx[] = {1, 0};

	rep (i, H) rep (j, W) {
		rep (k, 2) {
			int ny = i + dy[k];
			int nx = j + dx[k];

			if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;

			if (G[i][j] == G[ny][nx]) {
				if (uf.same(i * W + j, ny * W + nx)) {
					cout << "possible" << endl;	
					return 0;
				} else {
					uf.unite(i * W + j, ny * W + nx);
				}
			}
		}
	}

	cout << "impossible" << endl;

	return 0;
}
0