結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 13:58:55 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 156 ms / 3,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 12,279 ms |
コンパイル使用メモリ | 297,344 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 13:59:38 |
合計ジャッジ時間 | 18,189 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
DY = [1, 0, -1, 0]DX = [0, 1, 0, -1]n, m, k = read_line.split.map(&.to_i)a = Array.new(n) { read_line.split.map(&.to_i) }lo = 1hi = 1_000_000_001while hi - lo > 1mid = (lo + hi) // 2if count(a, mid) <= klo = midelsehi = midendendputs lodef count(a, v)h = a.sizew = a[0].sizeq = Deque(Tuple(Int32, Int32)).newc = Array.new(h) { Array.new(w, -1) }c[0][0] = a[0][0] < v ? 1 : 0q << {0, 0}while !q.empty?y, x = q.shift4.times do |d|ny = y + DY[d]nx = x + DX[d]if 0 <= ny < h && 0 <= nx < w && c[ny][nx] == -1if a[ny][nx] < vc[ny][nx] = c[y][x] + 1q << {ny, nx}elsec[ny][nx] = c[y][x]q.unshift({ny, nx})endendendendc[-1][-1]end