結果

問題 No.157 2つの空洞
ユーザー te-shte-sh
提出日時 2016-08-31 02:11:01
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,008 bytes
コンパイル時間 859 ms
コンパイル使用メモリ 128,044 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 03:57:27
合計ジャッジ時間 1,736 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import std.algorithm, std.array, std.container, std.range;
import std.numeric, std.math, std.bigint, std.bitmanip, std.random;
import std.string, std.conv, std.stdio, std.typecons;

alias Tuple!(int, "x", int, "y") point;

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

  auto visited = new bool[][](h, w);
  auto ci = searchCavities(w, h, m, visited);

  auto r = int.max;
  foreach (p1; ci[0])
    foreach (p2; ci[1]) {
      auto d = (p1.x - p2.x).abs + (p1.y - p2.y).abs;
      if (d < r) r = d;
    }

  writeln(r - 1);
}

point[][] searchCavities(int w, int h, bool[][] m, bool[][] visited)
{
  point find() {
    foreach (i; 0..m.length)
      foreach (j; 0..m[i].length)
        if (isCand(point(j.to!int, i.to!int), m, visited))
          return point(j.to!int, i.to!int);
    return point(-1, -1);
  }

  auto r = new point[][](0);
  while (true) {
    auto pf = find();
    if (pf.x < 0 || pf.y < 0)
      break;

    r ~= new point[](0);
    visited[pf.y][pf.x] = true;

    auto stack = SList!(point)(pf);
    while (!stack.empty) {
      auto p = stack.front;
      r.back ~= p;
      stack.removeFront;

      point p2;

      p2 = point(p.x - 1, p.y);
      if (p.x > 0 && isCand(p2, m, visited)) {
        stack.insertFront(p2);
        visited[p.y][p.x - 1] = true;
      }

      p2 = point(p.x + 1, p.y);
      if (p.x < w - 1 && isCand(p2, m, visited)) {
        stack.insertFront(p2);
        visited[p.y][p.x + 1] = true;
      }

      p2 = point(p.x, p.y - 1);
      if (p.y > 0 && isCand(p2, m, visited)) {
        stack.insertFront(p2);
        visited[p.y - 1][p.x] = true;
      }

      p2 = point(p.x, p.y + 1);
      if (p.y < h - 1 && isCand(p2, m, visited)) {
        stack.insertFront(p2);
        visited[p.y + 1][p.x] = true;
      }
    }
  }

  return r;
}

bool isCand(point p, bool[][] m, bool[][] visited)
{
  return m[p.y][p.x] && !visited[p.y][p.x];
}
0