⏹️
[ABC357 C] Sierpinski carpet
シェルピンスキーのカーペットをテキストとして書く問題。
アルゴリズム
ルービックキューブのような 9 個のセルで構成する面をイメージした上で、
- 9 個のセルを順に走査する
- 中央のセルだけ塗り潰す
- それ以外のセルには再度 (1) から適用する
グラフィック版との違い
- 描画する領域を
3**N
x3**N
で用意する - rectangle は、その領域に対して書き込む
あとはほぼ同じコードになる。
実装 (AC)
141 ms
class SierpinskiCarpet
EDGE = 3
def initialize(n)
@n = n
@field = Array.new(EDGE**@n) { Array.new(EDGE**@n) }
end
def call
draw(0, 0, EDGE**@n, @n)
end
def draw(x0, y0, size, depth)
if depth <= 0
return
end
size /= EDGE
EDGE.times do |y|
EDGE.times do |x|
x1 = x0 + x * size
y1 = y0 + y * size
if x == EDGE / 2 && y == EDGE / 2
rectangle(x1, y1, size)
next
end
draw(x1, y1, size, depth - 1)
end
end
end
def to_s
@field.collect { |row|
row.collect { |cell| cell ? "." : "#" }.join
}.join("\n")
end
private
def rectangle(x0, y0, size)
size.times do |y|
size.times do |x|
@field[y0 + y][x0 + x] = true
end
end
end
end
N = gets.to_i # => 3
puts SierpinskiCarpet.new(N).tap(&:call)
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > ###...######...######...###
# > #.#...#.##.#...#.##.#...#.#
# > ###...######...######...###
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > #########.........#########
# > #.##.##.#.........#.##.##.#
# > #########.........#########
# > ###...###.........###...###
# > #.#...#.#.........#.#...#.#
# > ###...###.........###...###
# > #########.........#########
# > #.##.##.#.........#.##.##.#
# > #########.........#########
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
# > ###...######...######...###
# > #.#...#.##.#...#.##.#...#.#
# > ###...######...######...###
# > ###########################
# > #.##.##.##.##.##.##.##.##.#
# > ###########################
関連
Discussion