hw = gets.split(" ").map(&:to_i) @h = hw[0] @w = hw[1] sg = gets.split(" ").map(&:to_i) @s = sg[0] - 1 + (sg[1] - 1) * @h #p @s sx = sg[0] sy = sg[1] @s = [sx, sy] @g = sg[2] - 1 + (sg[3] - 1) * @h #p @g gx = sg[2] gy = sg[3] @g = [gx, gy] @maze = [] @h.times do @maze << gets.strip.split('').map(&:to_i) #p @maze end @maze.flatten! #p @maze def dfs(pos, path) x = pos[0] y = pos[1] #p path [[1, 0], [0, -1], [-1,0], [0, 1]].each do |dir| dx = dir[0] dy = dir[1] next_x = x + dx next_y = y + dy #print "#{x},#{y} -> #{next_x}, #{next_y}\n" #next_pos = pos + dx + dy * @w #return if next_pos == @g #next if next_pos < 0 || next_pos >= @h * @w next if next_x < 1 || next_x > @h || next_y < 1 || next_y > @w next_pos = [next_x, next_y] next if path.include?(next_pos) # next if @maze[next_x - 1 + next_y * @w] #p @maze[(next_x - 1) * @w + next_y - 1] next if (@maze[(next_x - 1) * @w + next_y - 1] - @maze[(x - 1) * @w + y - 1]).abs > 1 if @s == [next_x, next_y] puts "YES" exit end #p dir #p next_pos path << next_pos dfs(next_pos, path.clone) end [[1, 0], [0, -1], [-1,0], [0, 1]].each do |dir| dx = dir[0] dy = dir[1] next_x = x + 2 * dx next_y = y + 2 * dy #print "#{x},#{y} -> #{next_x}, #{next_y}\n" next if next_x < 1 || next_x > @h || next_y < 1 || next_y > @w next_pos = [next_x, next_y] next if path.include?(next_pos) next if @maze[(x + dx - 1) * @w + (y + dy) - 1] >= @maze[(x - 1) * @w + y - 1] next if @maze[(next_x - 1) * @w + next_y - 1] != @maze[(x - 1) * @w + y - 1] if @s == [next_x, next_y] puts "YES" exit end #p dir #p next_pos #print "Bridge #{x}, #{y} -> #{next_x}, #{next_y}\n" path << next_pos dfs(next_pos, path.clone) end end next_x = 2 next_y = 5 #p @maze[(next_x - 1) * @w + next_y - 1] #exit if @s == @g puts "YES" exit end path = [@g] dfs(path[0], path.clone) puts "NO"