読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

再帰の練習

このあいだ買ったKindle本「Algorithmic Puzzles」より、つーかよくある問題だな。

Cover a 2^n ×2^n board missing one square with right trominoes, which are L-shaped tiles formed by three adjacent squares. The missing square can be any of the board squares. Trominoes should cover all the squares except the missing one exactly with no overlaps.

ようは、2^n*2^nのボートが与えられて、あるひとつのセル以外をL字のとろみのでカバーしてね、オーバーラップは無しよ、という問題。
ありがちー、だが基本ができていない俺には難問。特にコーディングw
色々解き方があると思うんだけど、この場合はうまい解法があった。(x,y)がボードの第何象限にあるかチェックした後その象限に載らないようにボードの中央にとろみのを載せて、
第1〜4象限まですべて一つのセルが欠けた状態にすればOK。
次にそれぞれの象限をよく見ると、それぞれ1つカバーしなくていいセルがある2^(n-1)*2^(n-1)のボードに対してL字とろみのでカバーすれば良いことがわかる。
ってこれさっきやったような・・・ということで再帰で書けば良さげ。書いてみたのは次の通り。なんか同じコードがたくさんあり嫌な感じ。
でもどうしていいのか正直よくわかんない。アホアホでbuggyなのはわかっているのだが・・・、もしテストケース通らなかったらデバッグ大変のパターンw

入力:n,x,y
ボードは2^nのサイズ、(x,y)が指定されたセル
出力:同じセルは同じアルファベットで表示

n,x,y=gets.split.map(&:to_i)
@trominos=[*?A..?Z,*?0..?9,*?a..?z]
@board=Array.new(2**n){Array.new(2**n,nil)}
@board[x][y]=?@
#2|1
#3|4
def which_quadrant(x,y,m,p,q)
	p-=x
	q-=y
	m-=1
	if p<2**m
		return q<2**m ? 2 : 3
	else
		return q<2**m ? 1 : 4
	end 
end

#fill @board[x..x*2**m-1,y..y+2**m-1] by tromino without p,q
def fill(x,y,m,p,q)
	if m>0
		w=which_quadrant(x,y,m,p,q)
		m-=1
		d=2**m
		ch=@trominos.shift
		case w
		when 1
			@board[x+d][y+d]=ch
			@board[x+d-1][y+d]=ch
			@board[x+d-1][y+d-1]=ch
			fill(x+d,y,m,p,q)
			fill(x+d,y+d,m,x+d,y+d)
			fill(x,y+d,m,x+d-1,y+d)
			fill(x,y,m,x+d-1,y+d-1)
		when 2
			@board[x+d][y+d]=ch
			@board[x+d-1][y+d]=ch
			@board[x+d][y+d-1]=ch
			fill(x,y,m,p,q)
			fill(x+d,y+d,m,x+d,y+d)
			fill(x,y+d,m,x+d-1,y+d)
			fill(x+d,y,m,x+d,y+d-1)	
		when 3
			@board[x+d][y+d]=ch
			@board[x+d-1][y+d-1]=ch
			@board[x+d][y+d-1]=ch
			fill(x,y+d,m,p,q)
			fill(x+d,y+d,m,x+d,y+d)
			fill(x,y,m,x+d-1,y+d-1)
			fill(x+d,y,m,x+d,y+d-1)
		when 4
			@board[x+d-1][y+d]=ch
			@board[x+d-1][y+d-1]=ch
			@board[x+d][y+d-1]=ch
			fill(x+d,y+d,m,p,q)
			fill(x,y+d,m,x+d-1,y+d)
			fill(x,y,m,x+d-1,y+d-1)
			fill(x+d,y,m,x+d,y+d-1)
		end
	end
end


fill(0,0,n,x,y)
@board.each{|row|puts row*""}

3 1 2
EECCPPOO
EB@CPLLO
FBBDMMLN
FFDDAMNN
TTRAAHJJ
TQRRHHGJ
UQQSKGGI
UUSSKKII

3 7 7
OONNKKJJ
OLLNKGGJ
PLMMHHGI
PPMAAHII
TTRAEEDD
TQRREBBD
UQQSFBCC
UUSSFFC@