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