結果

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

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

ソースコード

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