不格好エンジニア (引っ越しました)

wordpress.comから引っ越しました。

RubyでTopCoderの問題を解いてみる(深さ優先探索)

TopCoder SRM425 Div2 Level1を解いてみました。

※旧ブログからの転載記事です。

[問題要約]
東西南北自由に動き回るロボットが指定回数動いたときに、同じ地点に戻ってこない確率を求めよ。

ここでは深さ優先探索を用いてロボットの歩行パターンを列挙し、最後に結果をまとめています。
深さ優先探索を、はじめて実装しました。

class CrazyBot
# class variable
@@grid = Array.new(100).map{Array.new(100, false)}
@@vx = [1,-1,0,0]
@@vy = [0,0,1,-1]
@@prob = Array.new(4).map{0}


#
#= 成功する確率を求める
#
def get_probability(n, east, west, south, north)

@@prob[0] = east / 100.0
@@prob[1] = west / 100.0
@@prob[2] = south / 100.0
@@prob[3] = north / 100.0

pp @@prob

return dfs(50,50,n)

end

#
#= 深さ優先探索
#
def dfs(x, y, n)
return 0 if @@grid[x][y] # 既に通過している
return 1 if n == 0 # 探索しつくした

#pp "dfs x=#{x}, y=#{y}, n=#{n}"

@@grid[x][y] = true # 通過したら印をつける
ret = 0

for i in 0..3 do
ret += dfs(x+@@vx[i], y+@@vy[i], (n-1)) * @@prob[i]
end

@@grid[x][y] = false # 探索が終わって、上に戻ったら印を消す
return ret

end

end

crazy_bot = CrazyBot.new
# example1
pp "correct" if 1.0 == crazy_bot.get_probability(1,25,25,25,25)

# example2
pp "correct" if 0.75 == crazy_bot.get_probability(2,25,25,25,25)

# example3
pp "correct" if 1.0 == crazy_bot.get_probability(7,50,0,0,50)