$w, $h, = gets.split.map(&:to_i) $list = $h.times.map { gets.split.map(&:to_i) } $check_list = Array.new($h) {Array.new($w, false)} def check_loop(x, y) if $check_list[y][x] return false end check_point(x, y) end def check_point(x, y, pre = nil) if $check_list[y][x] return true end $check_list[y][x] = true if pre != :r && x > 0 && $list[y][x] == $list[y][x - 1] if check_point(x - 1, y, :l) return true end end if pre != :d && y > 0 && $list[y][x] == $list[y - 1][x] if check_point(x, y - 1, :u) return true end end if pre != :l && x < $w - 1 && $list[y][x] == $list[y][x + 1] if check_point(x + 1, y, :r) return true end end if pre != :u && y < $h - 1 && $list[y][x] == $list[y + 1][x] if check_point(x, y + 1, :d) return true end end return false end looped = false $h.times do |y| $w.times do |x| if check_loop(x, y) looped = true break end if looped break end end end require 'pp' pp $list pp $check_list if looped puts 'possipble' else puts 'impossible' end