結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー te-sh
提出日時 2017-08-21 17:10:50
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 384 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 814 ms
コンパイル使用メモリ 105,920 KB
実行使用メモリ 93,504 KB
最終ジャッジ日時 2024-06-12 21:42:40
合計ジャッジ時間 3,497 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

void main()
{
  auto rd = readln.split.to!(int[]), h = rd[0]+4, w = rd[1]+4;

  auto s = new string[](h);
  s[0] = s[1] = s[$-1] = s[$-2] = '.'.repeat(w).array;
  foreach (r; 2..h-2) s[r] = ".." ~ readln.chomp ~ "..";

  auto g = new int[][](h, w);

  auto q = Queue!int(h*w);

  foreach (r; 0..h)
    foreach (c; 0..w)
      if (s[r][c] == '.') {
        g[r][c] = 1;
        if (r > 0 && r < h-1 && c > 0 && c < w-1)
          q.insertBack(c << 12 | r);
      }

  while (!q.empty) {
    auto p = q.front; q.removeFront();
    auto c = p >> 12, r = p & ((1 << 12) - 1);
    foreach (ir; -1..2)
      foreach (ic; -1..2) {
        auto nc = c + ic, nr = r + ir;
        if (!g[nr][nc]) {
          g[nr][nc] = g[r][c] + 1;
          q.insertBack(nc << 12 | nr);
        }
      }
  }

  auto d = 0;
  foreach (r; 2..h-2)
    foreach (c; 2..w-2)
      d = max(d, g[r][c]);

  writeln(d-1);
}

struct Queue(T)
{
  T[] buf;
  size_t s, t;

  this(size_t n) { buf = new T[](n); }
  auto empty() { return s == t; }
  auto front() { return buf[s]; }
  auto removeFront() { ++s; }
  auto insertBack(T v) { buf[t++] = v; }
}
0