class Point
	attr_reader :x
	attr_reader :y
	
	def initialize(x, y)
		@x = x
		@y = y
	end
	
	def ==(pt)
		return (@x == pt.x && @y == pt.y)
	end
	
	def near(pt)
		return ( (@x-pt.x).abs <= 1 && (@y-pt.y).abs <= 1)
	end

	def nearAny(list)
		list.each do | pt |
			if(near(pt))
				return true
			end
		end
		return false
	end
	
end

class Grid
	def initialize(width, height)
		@width = width
		@height = height
		@cells = Array.new(@height * @width, false)
	end
	
	def isEmpty(pt)
		return !@cells[getOffset(pt)]
	end
	
	def set(pt)
		@cells[getOffset(pt)] = true
		nil
	end
	
	def getEmptyCells
		empty = Array.new
		@height.times do | y |
			@width.times do | x |
				pt = Point.new(x,y)
				if(isEmpty(pt))
					empty << pt
				end
			end
		end
		return empty
	end
	
	def getFirstEmptyArea(empty)
		area = Array.new
		empty.each do | pt |
			if(area.size == 0 || pt.nearAny(area))
				area << pt
			end
		end
		return area
	end
	
	def getBiggestEmptyArea
		biggest = Array.new
		empty = getEmptyCells
		while(empty.size > 0)
			thisArea = getFirstEmptyArea(empty)
			thisArea.each do | pt |
				empty.delete(pt)
			end
			if(thisArea.size > biggest.size)
				biggest = thisArea
			end
		end
		return biggest
	end
	
	def getOffset(pt)
		return pt.y * @width + pt.x
	end
end