Submission #20209546

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void yes(){ cout << "yes" << endl; }
void Yes(){ cout << "Yes" << endl; }
void YES(){ cout << "YES" << endl; }
void no(){ cout << "no" << endl; }
void No(){ cout << "No" << endl; }
void NO(){ cout << "NO" << endl; }
#define rep(i, n)for(int i=0; i<n; i++)
#define ll long long

ll INF = 1000000007;

ll H, W;

// (h, w)が領域に収まっていればtrue
bool included(ll h, ll w){
  bool ret = false;
  if(0 <= h && h <H && 0 <= w && w < W){
    ret = true;
  }
  return ret;
}


int main(){
  cin >> H >> W;
  char A[H][W];
  rep(i, H)
    rep(j, W)
    cin >> A[i][j];
  //

  // 4近傍を見る
  ll hy[] = {0, -1, 0, 1};
  ll wx[] = {1, 0, -1, 0};

  ll ans = 0;

  // 黒マスをキューに入れる
  // 黒マスの数をカウント
  queue<pair<ll, ll>> q;
  ll black_num = 0;
  bool visited[H][W];
  rep(i, H){
    rep(j, W){
      visited[i][j] = false;
    }
  }
  
  rep(i, H){
    rep(j, W){
      if(A[i][j] == '#'){
	q.push(make_pair(i, j) );
	visited[i][j] = true;
	black_num++;
      }
    }
  }

  while(black_num < H*W){
    ll num = q.size();
    for(ll i = 0; i<num; i++){
      ll y = q.front().first, x = q.front().second;
      q.pop();
      // 4近傍を見る
      for(ll k=0; k<4; k++){
	// 次の点を処理
	ll ny = y + hy[k], nx = x + wx[k];
	// 領域におさまっている，かつ未訪問
	if(included(ny, nx) ){
	  if(!visited[ny][nx]){
	    q.push(make_pair(ny, nx) );
	    visited[ny][nx] = true;
	    black_num++;
	  }
	}
      }
    } // for( auto )
    
    ans++;
  }

  
  cout <<  ans << endl;
  
  return 0;
}

Submission Info

Judge Result