結果

問題 No.157 2つの空洞
ユーザー te-sh
提出日時 2016-08-31 02:11:01
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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