「 今週のお題:道順は違っても結果は同じ」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 格子状のマス目 ( の一部 ) がある時に、上下左右で全てのマスを1度ずつ通る経路が何通りあるかを出力する
- マス目の配置については、全てのマスを通る1つの経路が入力される。例えば、問題の例にあった次の図のようなマスの配置であれば、左側のような経路があるため、「上左下左」ということで“ULDL”という入力となる。( その他、「右右上左」の“RRUL”等もありうる )
解説
入力文字列から、格子情報を構築し、スタート地点毎に経路数を加算していく再帰で解きました。
入力文字列を全て見ないと、有効なマスのある縦横のサイズが分からないため、文字列処理中に動的に拡張して格子情報を構築しています。
なお、端の処理を簡略化するため、上下左右の端にダミー領域を設けます。
経路探索では、既に通ったマスをビットマスクで管理します。
全部のマスを通るということは、通るマス数が一定になるので、再帰する際に残りのマス数を引数とし、最後のマスかどうかをチェックしています。
# 入力文字列から格子中の通ったマスを記録する関数 def makemap(s) m=[[true]] # 現在地 x=y=0 # 左右・上下のサイズ xlim=ylim=1 # 有効なマス数 ( 重複したマスを辿らない前提 ) n=s.size+1 s.chars.each{|c| case c when ?U if y==0 # 上端のため、全体を下にシフト m.unshift([false]*xlim) m[0][x]=true ylim+=1 else m[y-=1][x]=true end when ?D if (y+=1)==ylim # 下端のため、行を追加 m.push([false]*xlim) m[y][x]=true ylim+=1 else m[y][x]=true end when ?L if x==0 # 左端のため、全体を右にシフト m.each{|r|r.unshift(false)} m[y][0]=true xlim+=1 else m[y][x-=1]=true end when ?R if (x+=1)==xlim # 右端のため、列を追加 m.each{|r|r.push(false)} m[y][x]=true xlim+=1 else m[y][x]=true end end } # ダミー領域を上下左右の端に追加 m.each{|r| r.unshift(false) r.push(false) } m.unshift([false]*(xlim+2)) m.push([false]*(xlim+2)) # 二次元リストおよび、ダミー領域を除く範囲のサイズ、有効なマスの数を返す [m,xlim,ylim,n] end def solve(m,xlim,ylim,n) # 経路の数 a=0 # 再帰的に経路を調べる関数 f=->x,y,mask,r{ # 有効なマスでなければ打ち切り return unless m[y][x] # 既に通ったマスなら打ち切り return if mask[y*xlim+x]!=0 # 重複なく最後まで来たら経路数をカウント if (r-=1)==0 a+=1 return end # 現在地をマスクに登録して、上下左右に再帰 mask|=1<<(y*xlim+x) f[x,y-1,mask,r] f[x,y+1,mask,r] f[x-1,y,mask,r] f[x+1,y,mask,r] } # それぞれの開始地点に対し、f を実行 1.upto(ylim){|ys| 1.upto(xlim){|xs| f[xs,ys,0,n] } } # 経路数を返す a end puts solve(*makemap(gets.chomp))
終わりに
本当のところを言うと、行き・帰りがちょうど逆になる経路半分だけ数えて倍にするとか、入力で与えられた経路の端を調べて、袋小路になっていたらそこが必ず端になるだろう、とか、効率を上げる方法は色々ありそうだったのですが…。まあ、これで間に合ってるからいっか、的な。