#include #include #include #include #include using namespace std; int vector_finder(vector 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 BFS(vector V, int W, int H) { queue Q; map S; vector 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 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 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 T; while (flag) { k++; vector 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; }