「 今週のお題：道順は違っても結果は同じ」問題解答 ( 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))
終わりに
本当のところを言うと、行き・帰りがちょうど逆になる経路半分だけ数えて倍にするとか、入力で与えられた経路の端を調べて、袋小路になっていたらそこが必ず端になるだろう、とか、効率を上げる方法は色々ありそうだったのですが…。まあ、これで間に合ってるからいっか、的な。
