結果

問題 No.157 2つの空洞
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-06-15 21:53:28
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,650 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 52,844 KB
最終ジャッジ日時 2024-11-14 19:04:19
合計ジャッジ時間 982 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:16:1: error: ‘vector’ does not name a type
   16 | vector<int> dr = {0, 0, 1, -1},
      | ^~~~~~
main.cpp:16:31: error: expected unqualified-id before ‘,’ token
   16 | vector<int> dr = {0, 0, 1, -1},
      |                               ^
main.cpp:17:16: error: expected constructor, destructor, or type conversion before ‘=’ token
   17 |             dc = {1, -1, 0, 0};
      |                ^
main.cpp:20:1: error: ‘vector’ does not name a type
   20 | vector<string> kort;
      | ^~~~~~
main.cpp:22:24: error: ‘vector’ has not been declared
   22 | void dfs(int r, int c, vector<Point> &holes) {
      |                        ^~~~~~
main.cpp:22:30: error: expected ‘,’ or ‘...’ before ‘<’ token
   22 | void dfs(int r, int c, vector<Point> &holes) {
      |                              ^
main.cpp: In function ‘void dfs(int, int, int)’:
main.cpp:23:3: error: ‘kort’ was not declared in this scope
   23 |   kort[r][c] = '#';
      |   ^~~~
main.cpp:24:3: error: ‘holes’ was not declared in this scope
   24 |   holes.push_back(Point(r, c));
      |   ^~~~~
main.cpp:25:21: error: ‘dr’ was not declared in this scope; did you mean ‘r’?
   25 |   for(int i : range(dr.size())) {
      |                     ^~
      |                     r
main.cpp:27:18: error: ‘dc’ was not declared in this scope; did you mean ‘nc’?
   27 |     int nc = c + dc[i];
      |                  ^~
      |                  nc
main.cpp: In function ‘Point find_hole()’:
main.cpp:39:10: error: ‘kort’ was not declared in this scope
   39 |       if(kort[r][c] == '.') {
      |          ^~~~
main.cpp: In function ‘int main()’:
main.cpp:52:3: error: ‘kort’ was not declared in this scope
   52 |   kort.assign(h, string());
      |   ^~~~
main.cpp:53:3: error: ‘vector’ was not declared in this scope
   53 |   vector<Point> holes1, holes2;
      |   ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<ve

ソースコード

diff # 

#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