結果

問題 No.157 2つの空洞
ユーザー te-shte-sh
提出日時 2017-02-03 15:49:24
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,494 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 102,336 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-03 01:18:46
合計ジャッジ時間 1,870 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 4 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap

alias Point!int point;
alias sibPoints!int sibs;

void main()
{
  auto rd = readln.split.to!(int[]), w = rd[0], h = rd[1];
  auto cij = h.iota.map!(_ => readln.chomp).array;

  auto vij = new bool[][](h, w);
  foreach (y; h.iota) vij[y][0] = vij[y][w-1] = true;
  foreach (x; w.iota) vij[0][x] = vij[h-1][x] = true;

  auto wij = new bool[][](h, w);

  auto availableSibs(point p) {
    return sibs.map!(a => p + a)
      .filter!(np => np.x >= 0 && np.y >= 0 && np.x < w && np.y < h);
  }

  auto findEmpty() {
    foreach (y; 1..h-1)
      foreach (x; 1..w-1)
        if (cij[y][x] == '.' && !wij[y][x]) return point(x, y);
    return point(-1, -1);
  }

  auto distanceTo1(point s) {
    auto xij = new bool[][](h, w);
    xij[s.y][s.x] = true;

    point[] pi = [s];
    auto r = 1;
    while (!pi.empty) {
      point[] npi;
      foreach (p; pi) {
        foreach (np; availableSibs(p)) {
          if (wij[np.y][np.x]) return r;
          if (cij[np.y][np.x] != '#' || xij[np.y][np.x]) continue;
          xij[np.y][np.x] = true;
          npi ~= np;
        }
      }
      pi = npi;
      ++r;
    }
    return int.max;
  }

  auto s1 = findEmpty;
  vij[s1.y][s1.x] = wij[s1.y][s1.x] = true;

  auto qi1 = SList!point(s1);
  while (!qi1.empty) {
    auto p = qi1.front; qi1.removeFront;
    foreach (np; availableSibs(p)) {
      if (cij[np.y][np.x] != '.' || vij[np.y][np.x]) continue;
      vij[np.y][np.x] = wij[np.y][np.x] = true;
      qi1.insertFront(np);
    }
  }

  auto s2 = findEmpty;
  vij[s2.y][s2.x] = true;

  auto r = int.max;
  auto qi2 = SList!point(s2);
  while (!qi2.empty) {
    auto p = qi2.front; qi2.removeFront;
    foreach (np; availableSibs(p)) {
      if (vij[np.y][np.x]) continue;
      vij[np.y][np.x] = true;
      if (cij[np.y][np.x] == '#')
        r = min(r, distanceTo1(np));
      else
        qi2.insertFront(np);
    }
  }

  writeln(r);
}

struct Point(T) {
  T x, y;

  auto opBinary(string op: "+")(Point!T rhs) { return Point!T(x + rhs.x, y + rhs.y); }
  auto opBinary(string op: "-")(Point!T rhs) { return Point!T(x - rhs.x, y - rhs.y); }
  auto opBinary(string op: "*")(Point!T rhs) { return x * rhs.x + y * rhs.y; }
  auto opBinary(string op: "*")(T a) { return Point!T(x * a, y * a); }

  T hypot2() { return x ^^ 2 + y ^^ 2; }
}

const auto sibPoints(T) = [Point!T(-1, 0), Point!T(0, -1), Point!T(1, 0), Point!T(0, 1)];
0