結果
問題 |
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 = 1 hi = 1_000_000_001 while hi - lo > 1 mid = (lo + hi) // 2 if count(a, mid) <= k lo = mid else hi = mid end end puts lo def count(a, v) h = a.size w = a[0].size q = Deque(Tuple(Int32, Int32)).new c = Array.new(h) { Array.new(w, -1) } c[0][0] = a[0][0] < v ? 1 : 0 q << {0, 0} while !q.empty? y, x = q.shift 4.times do |d| ny = y + DY[d] nx = x + DX[d] if 0 <= ny < h && 0 <= nx < w && c[ny][nx] == -1 if a[ny][nx] < v c[ny][nx] = c[y][x] + 1 q << {ny, nx} else c[ny][nx] = c[y][x] q.unshift({ny, nx}) end end end end c[-1][-1] end