結果

問題 No.697 池の数はいくつか
ユーザー KazunKazun
提出日時 2020-06-03 01:10:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,832 bytes
コンパイル時間 2,089 ms
コンパイル使用メモリ 104,640 KB
実行使用メモリ 814,784 KB
最終ジャッジ日時 2024-11-25 16:15:30
合計ジャッジ時間 81,352 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
62,888 KB
testcase_01 AC 2 ms
62,832 KB
testcase_02 AC 2 ms
62,960 KB
testcase_03 AC 2 ms
62,828 KB
testcase_04 AC 2 ms
62,840 KB
testcase_05 MLE -
testcase_06 AC 2 ms
13,636 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,816 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 1 ms
6,816 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 2 ms
6,816 KB
testcase_23 AC 2 ms
6,816 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 -
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
	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++;
		T = BFS(V, 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