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)