require 'set' H, W = gets.split.map(&:to_i) class << MAP = Array.new(H) { gets.strip } def ok?(dx, dy) d = dy * W + dx bs = blacks - blacks.map {|i| i + d if i % W + dx < W } bs.size == blacks.size / 2 && bs.all? {|i| flat[i + d] == 35 } end def solve ax, ay, bx, by = aabb (1..by - ay).each do |dy| return :YES if ok?(0, dy) end (1..bx - ax).each do |dx| (0..by - ay).each do |dy| return :YES if ok?(dx, dy) end end :NO end def flat @flat ||= map(&:bytes).flatten end def blacks @blacks ||= Set.new(flat.each_with_index.map {|cell, i| i if cell == 35 }.compact) end def aabb ax = ay = bx = by = nil blacks.each do |i| y, x = i.divmod(W) ax = x if !ax || ax > x ay = y if !ay || ay > y bx = x if !bx || bx < x by = y if !by || by < y end return ax, ay, bx, by end end puts MAP.solve