結果

問題 No.697 池の数はいくつか
ユーザー Kazun
提出日時 2020-06-03 01:27:16
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 1,915 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,750 ms
コンパイル使用メモリ 99,868 KB
実行使用メモリ 814,964 KB
最終ジャッジ日時 2024-11-25 16:17:17
合計ジャッジ時間 80,429 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 10 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

int vector_finder(vector<int> vec, int number) {
	auto itr =find(vec.begin(), vec.end(), number);
	size_t index =distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return true;
	}
	else { // 発見できなかったとき
		return false;
	}
}
vector<int> BFS(vector<int> V, int W, int H) {
	queue<int> Q;
	map<int, int> S;
	vector<int> T;

	int v, w;

	for (int i = 0; i < V.size(); i++) {
		S[V.at(i)] = false;
	}
	Q.push(V.at(0));
	S[V.at(0)] = true;
	T.push_back(V.at(0));

	while (Q.size()!=0) {		
		v = Q.front();
		Q.pop();

		if (vector_finder(V, v + 1)) {
			if (S.at(v + 1) == false) {
				Q.push(v + 1);
				T.push_back(v + 1);
				S.at(v + 1) = true;
			}
		}

		if (vector_finder(V, v - 1)) {
			if (!S.at(v - 1)) {
				Q.push(v - 1);
				T.push_back(v - 1);
				S.at(v - 1) = true;
			}
		}

		if (vector_finder(V, v + (W + 2))) {
			if (!S.at(v + (W + 2))) {
				Q.push(v + (W + 2));
				T.push_back(v + (W + 2));
				S.at(v + (W + 2)) = true;
			}
		}

		if (vector_finder(V, v - (W + 2))) {
			if (!S.at(v - (W + 2))) {
				Q.push(v - (W + 2));
				T.push_back(v - (W + 2));
				S.at(v - (W + 2)) = true;
			}
		}
	}
	return T;
}
int main() {
	int H, W;
	cin >> H >> W;
	
	int a;
	vector<int> V,X;
	for (int y = 1; y <= H; y++) {
		for (int x = 1; x <= W; x++) {
			cin >> a;
			if (a == 1) {
				V.push_back(y * (W + 2) + x);
			}
		}
	}

	map<int, bool> U;

	for (int i = 0; i < V.size(); i++) {
		U[V.at(i)] = false;
	}

	int flag =(V.size()!=0);
	int k = 0;
	int L = V.size();
	vector<int> T;

	while (flag) {
		k++;
		
		vector<int> X;
		for (int i = 0; i < L; i++) {
			X.push_back(V.at(i));
		}

		T = BFS(X, W, H);

		for (int j = 0; j < T.size(); j++) {
			remove(V.begin(), V.end(), T.at(j));
			L--;
		}
		flag = (L != 0);
	}

	cout << k << endl;
}
0