75 lines
1.5 KiB
Ruby
75 lines
1.5 KiB
Ruby
class Rectangle
|
|
DIRS = [[1, 0], [-1, 0], [0, -1], [0, 1]]
|
|
def initialize(h, w)
|
|
raise ArgumentError if (h.odd? and w.odd?) or h<=0 or w<=0
|
|
@h, @w = h, w
|
|
@limit = h * w / 2
|
|
end
|
|
|
|
def cut(disp=true)
|
|
@cut = {}
|
|
@select = []
|
|
@result = []
|
|
@grid = make_grid
|
|
walk(0,0)
|
|
display if disp
|
|
@result
|
|
end
|
|
|
|
def make_grid
|
|
Array.new(@h+1) {|i| Array.new(@w+1) {|j| true if i<@h and j<@w }}
|
|
end
|
|
|
|
def walk(y, x)
|
|
@grid[y][x] = @grid[@h-y-1][@w-x-1] = false
|
|
@select.push([y,x])
|
|
select = @select.sort
|
|
unless @cut[select]
|
|
@cut[select] = true
|
|
if @select.size == @limit
|
|
@result << select
|
|
else
|
|
search_next.each {|yy,xx| walk(yy,xx)}
|
|
end
|
|
end
|
|
@select.pop
|
|
@grid[y][x] = @grid[@h-y-1][@w-x-1] = true
|
|
end
|
|
|
|
def search_next
|
|
nxt = {}
|
|
@select.each do |y,x|
|
|
DIRS.each do |dy, dx|
|
|
nxt[[y+dy, x+dx]] = true if @grid[y+dy][x+dx]
|
|
end
|
|
end
|
|
nxt.keys
|
|
end
|
|
|
|
def display
|
|
@result.each do |select|
|
|
@grid = make_grid
|
|
select.each {|y,x| @grid[y][x] = false}
|
|
puts to_s
|
|
end
|
|
end
|
|
|
|
def to_s
|
|
text = Array.new(@h*2+1) {" " * (@w*4+1)}
|
|
for i in 0..@h
|
|
for j in 0..@w
|
|
text[i*2][j*4+1,3] = "---" if @grid[i][j] != @grid[i-1][j]
|
|
text[i*2+1][j*4] = "|" if @grid[i][j] != @grid[i][j-1]
|
|
text[i*2][j*4] = "+"
|
|
end
|
|
end
|
|
text.join("\n")
|
|
end
|
|
end
|
|
|
|
rec = Rectangle.new(2,2)
|
|
puts rec.cut.size
|
|
|
|
rec = Rectangle.new(3,4)
|
|
puts rec.cut.size
|