結果

問題 No.157 2つの空洞
コンテスト
ユーザー a01sa01to
提出日時 2025-10-30 00:35:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,747 bytes
コンパイル時間 3,568 ms
コンパイル使用メモリ 293,600 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-30 00:35:06
合計ジャッジ時間 4,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int w, h;
  cin >> w >> h;
  vector Grid(h, vector<char>(w));
  rep(i, h) rep(j, w) cin >> Grid[i][j];
  vector vis(h, vector<bool>(w, false));
  constexpr array<int, 4> dx = { 1, 0, -1, 0 };
  constexpr array<int, 4> dy = { 0, 1, 0, -1 };
  const auto inRange = [&](int i, int j) {
    return 0 <= i && i < h && 0 <= j && j < w;
  };
  {
    bool f = false;
    rep(i, h) {
      rep(j, w) {
        if (Grid[i][j] != '.') continue;
        queue<pair<int, int>> que;
        que.push({ i, j });
        vis[i][j] = true;
        while (!que.empty()) {
          auto [x, y] = que.front();
          que.pop();
          rep(d, 4) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!inRange(nx, ny)) continue;
            if (!vis[nx][ny] && Grid[nx][ny] == '.') {
              vis[nx][ny] = true;
              que.push({ nx, ny });
            }
          }
        }
        f = true;
        break;
      }
      if (f) break;
    }
  }
  vector dist(h, vector<int>(w, 1e9));
  queue<pair<int, int>> q;
  rep(i, h) rep(j, w) {
    if (vis[i][j]) dist[i][j] = 0, q.push({ i, j });
  }
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    rep(d, 4) {
      int nx = x + dx[d], ny = y + dy[d];
      if (!inRange(nx, ny)) continue;
      if (dist[nx][ny] > dist[x][y] + 1) {
        dist[nx][ny] = dist[x][y] + 1;
        q.push({ nx, ny });
      }
    }
  }
  int ans = 1e9;
  rep(i, h) rep(j, w) if (Grid[i][j] == '.' && !vis[i][j]) ans = min(ans, dist[i][j]);
  cout << ans - 1 << '\n';
  return 0;
}
0