結果

問題 No.402 最も海から遠い場所
ユーザー te-shte-sh
提出日時 2017-08-21 17:10:50
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 362 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 780 ms
コンパイル使用メモリ 91,308 KB
実行使用メモリ 94,272 KB
最終ジャッジ日時 2023-09-03 16:02:18
合計ジャッジ時間 3,344 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 10 ms
5,168 KB
testcase_16 AC 13 ms
7,244 KB
testcase_17 AC 144 ms
53,692 KB
testcase_18 AC 362 ms
93,776 KB
testcase_19 AC 187 ms
94,272 KB
testcase_20 AC 280 ms
92,104 KB
testcase_21 AC 182 ms
92,860 KB
権限があれば一括ダウンロードができます

ソースコード

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