結果

問題 No.13 囲みたい！
ユーザー ldsyb
提出日時 2017-07-18 20:50:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,056 bytes
コンパイル時間 859 ms
コンパイル使用メモリ 77,300 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-08 10:58:45
合計ジャッジ時間 1,825 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

constexpr int dd[] = {0, 1, 0, -1, 0};

bool inside(int a, int b, int alim, int blim){
	return 0 <= a && a < alim && 0 <= b && b < blim;
}

bool solve(vector<vector<int>> &vec, vector<vector<bool>> &done, int a, int b, int pre_a = -1, int pre_b = -1){
	done[a][b] = true;
	bool f = false;
	for(int i = 0; i < 4; i++){
		int next_a = a + dd[i], next_b = b + dd[i + 1];
		if(next_a == pre_a && next_b == pre_b) continue;
		if(inside(next_a, next_b, vec.size(), vec[0].size()) && vec[a][b] == vec[next_a][next_b]){
			if(done[next_a][next_b]) return true;
			f |= solve(vec, done, next_a, next_b, a, b);
		}
	}
	return f;
}

int main(){
	int w, h;
	cin >> w >> h;
	vector<vector<bool>> done(h, vector<bool>(w));
	vector<vector<int>> a(h, vector<int>(w));
	for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> a[i][j];
	for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) if(!done[i][j] && solve(a, done, i, j)){
		cout << "possible" << endl;
		return 0;
	}
	cout << "impossible" << endl;
}
0