struct Edge(T) getter to, wt def initialize(@to : Int32, @wt : T) end end def dijkstra(g : Array(Array(Edge(T))), s : Int32) forall T inf = T::MAX n = g.size d = Array.new(n, inf) d[s] = 0 heap = [] of Tuple(T, Int32) heap << {0, s} while !heap.empty? min_index = 0 heap.each_with_index do |(dist, _), i| min_index = i if dist < heap[min_index][0] end d0, u = heap.delete_at(min_index) next if d0 > d[u] g[u].each do |e| v = e.to new_dist = d[u] + e.wt if d[v] > new_dist d[v] = new_dist heap << {new_dist, v} end end end d end # Read input input = read_line.split.map(&.to_i) n, hp, ox, oy = input[0], input[1], input[2], input[3] ox -= 1 oy -= 1 # Read grid a = Array.new(n) { Array.new(n, 0) } n.times do |i| row = read_line.split.map(&.to_i) n.times do |j| a[i][j] = row[j] end end # Build graph g = Array.new(n * n) { [] of Edge(Int32) } n.times do |i| n.times do |j| if i < n - 1 g[i * n + j] << Edge.new((i + 1) * n + j, a[i + 1][j]) g[(i + 1) * n + j] << Edge.new(i * n + j, a[i][j]) end if j < n - 1 g[i * n + j] << Edge.new(i * n + (j + 1), a[i][j + 1]) g[i * n + (j + 1)] << Edge.new(i * n + j, a[i][j]) end end end # Run Dijkstra from start (0,0) d = dijkstra(g, 0) if hp > d[n * n - 1] puts "YES" exit end if ox == -1 puts "NO" exit end # Run Dijkstra from oasis d2 = dijkstra(g, oy * n + ox) if hp > d[oy * n + ox] && 2 * (hp - d[oy * n + ox]) > d2[n * n - 1] puts "YES" else puts "NO" end