SRM425 Div2 500

問題

壊れたロボットがある．このロボットはnステップランダムに進む．東西南北それぞれに進む確率が与えられるとき，ロボットが直線的(すでに通った場所を通らないの意味)に進む確率を求める．

考え方

dfsで通った場所をメモしながらそれぞれの方向に動いた時の確率を計算して，その確率の合計を返す．