結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
👑 |
提出日時 | 2019-07-19 23:18:49 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 1,989 ms / 3,000 ms |
コード長 | 1,856 bytes |
コンパイル時間 | 582 ms |
コンパイル使用メモリ | 5,504 KB |
実行使用メモリ | 403,968 KB |
最終ジャッジ日時 | 2024-12-26 04:04:12 |
合計ジャッジ時間 | 9,315 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
local ior = io.input()local h, w = ior:read("*n", "*n", "*l")local function getindex(i_h, i_w)return i_w + (i_h - 1) * wendlocal taskstate = {}for i = 1, h * w do taskstate[i] = false endlocal tasks = {}local tasknum = 0local done = 0local tasklim = h * wlocal function addtask(idx)if(not taskstate[idx]) thentaskstate[idx] = truetasknum = tasknum + 1local taskidx = tasknum % tasklimif taskidx == 0 then taskidx = tasklim endtasks[taskidx] = idxendendlocal function createMap()local str = ""local map = {}local inf = h + wfor i_h = 1, h dostr = ior:read()for i_w = 1, w dolocal index = getindex(i_h, i_w)if str:sub(i_w, i_w) == "#" thenif i_h == 1 or i_h == h or i_w == 1 or i_w == w thenmap[index] = 1addtask(index)elsemap[index] = infendelsemap[index] = 0addtask(index)endendendreturn mapendlocal map = createMap()local function walk(src, dst)if map[src] + 1 < map[dst] thenmap[dst] = map[src] + 1addtask(dst)endendwhile(done < tasknum) dodone = done + 1local taskidx = done % tasklimif(taskidx == 0) then taskidx = tasklim endlocal idx = tasks[taskidx]taskstate[idx] = falseif w < idx then walk(idx, idx - w) endif idx <= (h - 1) * w then walk(idx, idx + w) endif 1 < w thenif idx % w ~= 0 thenwalk(idx, idx + 1)if w < idx then walk(idx, idx + 1 - w) endif idx <= (h - 1) * w then walk(idx, idx + 1 + w) endendif idx % w ~= 1 thenwalk(idx, idx - 1)if w < idx then walk(idx, idx - 1 - w) endif idx <= (h - 1) * w then walk(idx, idx - 1 + w) endendendendlocal mma = math.maxlocal ret = 1for i = 1, h * w doret = mma(ret, map[i])endprint(ret)