結果
問題 | No.659 徘徊迷路 |
ユーザー |
👑 |
提出日時 | 2021-04-19 21:50:12 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,905 bytes |
コンパイル時間 | 71 ms |
コンパイル使用メモリ | 6,940 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 05:06:56 |
合計ジャッジ時間 | 1,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 12 |
ソースコード
local mfl = math.floor local h, w, tm = io.read("*n", "*n", "*n") local sr, sc = io.read("*n", "*n") local gr, gc = io.read("*n", "*n", "*l") local t = {} _u = io.read() for i = 2, h - 1 do local s = io.read() for j = 2, w - 1 do local idx = (i - 2) * (w - 2) + (j - 1) t[idx] = s:sub(j, j) == "." end end _u = io.read() h = h - 2 w = w - 2 local n = h * w local sidx = (sr - 1) * w + sc local gidx = (gr - 1) * w + gc local mat = {} for i = 1, n do mat[i] = {} for j = 1, n do mat[i][j] = 0 end end for i = 1, h do for j = 1, w do local idx = (i - 1) * w + j if t[idx] then local c = 0 if 1 < i and t[idx - w] then c = c + 1 end if i < h and t[idx + w] then c = c + 1 end if 1 < j and t[idx - 1] then c = c + 1 end if j < w and t[idx + 1] then c = c + 1 end if 0 < c then if 1 < i and t[idx - w] then mat[idx][idx - w] = 1 / c end if i < h and t[idx + w] then mat[idx][idx + w] = 1 / c end if 1 < j and t[idx - 1] then mat[idx][idx - 1] = 1 / c end if j < w and t[idx + 1] then mat[idx][idx + 1] = 1 / c end else mat[idx][idx] = 1 end end end end local remat = {} for i = 1, n do remat[i] = {} for j = 1, n do remat[i][j] = 0 end end local function matmat() for i = 1, n do for j = 1, n do local v = 0 for k = 1, n do v = v + mat[i][k] * mat[k][j] end remat[i][j] = v end end for i = 1, n do for j = 1, n do mat[i][j] = remat[i][j] end end end local vec, revec = {}, {} for i = 1, n do vec[i] = 0 revec[i] = 0 end local function vecmat() for i = 1, n do local v = 0 for k = 1, n do v = v + vec[k] * mat[k][i] end revec[i] = v end for i = 1, n do vec[i] = revec[i] end end vec[sidx] = 1 while 0 < tm do if tm % 2 == 1 then vecmat() end matmat() tm = mfl(tm / 2) end print(string.format("%.10f", vec[gidx]))