結果

問題 No.697 池の数はいくつか
ユーザー 👑 Kazun
提出日時 2020-06-03 01:10:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,832 bytes
コンパイル時間 1,448 ms
コンパイル使用メモリ 99,516 KB
最終ジャッジ日時 2025-01-10 20:45:06
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 16 TLE * 10 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0