結果
問題 | No.697 池の数はいくつか |
ユーザー |
👑 ![]() |
提出日時 | 2020-06-03 01:27:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 TLE * 10 MLE * 4 |
ソースコード
#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;}