結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
|
提出日時 | 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 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;import std.container; // SList, DList, BinaryHeapvoid 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; }}