結果

問題 No.157 2つの空洞
コンテスト
ユーザー yuppe19 😺
提出日時 2015-06-15 21:53:28
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,650 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 970 ms
コンパイル使用メモリ 174,972 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:02:44
合計ジャッジ時間 1,692 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:51:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |   scanf("%d%d", &w, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp: In function ‘Point find_hole()’:
main.cpp:45:22: warning: ‘pc’ may be used uninitialized [-Wmaybe-uninitialized]
   45 |   return Point(pr, pc);
      |                      ^
main.cpp:36:11: note: ‘pc’ was declared here
   36 |   int pr, pc;
      |           ^~
main.cpp:45:22: warning: ‘pr’ may be used uninitialized [-Wmaybe-uninitialized]
   45 |   return Point(pr, pc);
      |                      ^
main.cpp:36:7: note: ‘pr’ was declared here
   36 |   int pr, pc;
      |       ^~

ソースコード

diff #
raw source code 

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

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

class Point {
public:
  int r, c;
  Point(void) {}
  Point(int _r, int _c) { r = _r, c = _c; }
  bool operator==(const Point& other) const { return r == other.r && c == other.c; }
  int dist(const Point& other) const { return abs(r - other.r) + abs(c - other.c); }
};
vector<int> dr = {0, 0, 1, -1},
            dc = {1, -1, 0, 0};

int w, h;
vector<string> kort;

void dfs(int r, int c, vector<Point> &holes) {
  kort[r][c] = '#';
  holes.push_back(Point(r, c));
  for(int i : range(dr.size())) {
    int nr = r + dr[i];
    int nc = c + dc[i];
    if(nr < 0 || h <= nr || nc < 0 || w <= nc) { continue; }
    if(kort[nr][nc] == '.') {
      dfs(nr, nc, holes);
    }
  }
}

Point find_hole() {
  int pr, pc;
  for(int r : range(h)) {
    for(int c : range(w)) {
      if(kort[r][c] == '.') {
        pr = r, pc = c;
        break;
      }
    }
  }
  return Point(pr, pc);
}

const int inf = 987654321;

int main(void) {
  scanf("%d%d", &w, &h);
  kort.assign(h, string());
  vector<Point> holes1, holes2;
  for(int i : range(h)) { cin >> kort[i]; }
  Point h1 = find_hole();
  dfs(h1.r, h1.c, holes1);
  Point h2 = find_hole();
  dfs(h2.r, h2.c, holes2);
  int lag = inf;
  for(Point p1 : holes1) {
    for(Point p2 : holes2) {
      int dist = p1.dist(p2) - 1;
      lag = min(lag, dist);
    }
  }
  printf("%d\n", lag);
  return 0;
}
0