#491086 (C++14) No.697 池の数はいくつか

• 問題: No.697 池の数はいくつか
• ユーザー: Kazun
• 提出日時: 2020-06-03 01:27:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: MLE
• 実行時間: -
• コード長: 1,915 bytes
• コンパイル時間: 1,750 ms
• コンパイル使用メモリ: 99,868 KB
• 実行使用メモリ: 814,964 KB
• 最終ジャッジ日時: 2024-11-25 16:17:17
• 合計ジャッジ時間: 80,429 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 64,796 KB
testcase_01	AC	2 ms; 64,844 KB
testcase_02	AC	2 ms; 64,876 KB
testcase_03	AC	2 ms; 64,752 KB
testcase_04	AC	2 ms; 64,816 KB
testcase_05	MLE	-
testcase_06	MLE	-
testcase_07	MLE	-
testcase_08	AC	2 ms; 6,816 KB
testcase_09	AC	2 ms; 6,816 KB
testcase_10	AC	2 ms; 6,816 KB
testcase_11	AC	1 ms; 6,816 KB
testcase_12	AC	1 ms; 6,816 KB
testcase_13	AC	2 ms; 6,816 KB
testcase_14	AC	1 ms; 6,816 KB
testcase_15	AC	1 ms; 6,816 KB
testcase_16	AC	2 ms; 6,816 KB
testcase_17	AC	2 ms; 6,816 KB
testcase_18	AC	2 ms; 6,820 KB
testcase_19	AC	2 ms; 6,820 KB
testcase_20	AC	2 ms; 6,816 KB
testcase_21	AC	2 ms; 6,816 KB
testcase_22	AC	2 ms; 6,820 KB
testcase_23	AC	2 ms; 6,820 KB
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	MLE	-

ソースコード

#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;
}