First Knight (UVa Live Archive Europe Southwestern 2008)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2298

問題

m*nのグリッドがある。各マスで上下左右に移動する確率を与えるので、(1,1)から(m,n)まで行くのに掛かる時間の期待値を求めよ。
2<=m,n<=40
答えは1000000以下

解法

ガウスの消去法で連立方程式を計算する。これだとO(m^3n^3)だが、行列が帯行列であるということを使うとO(mn^3)で計算可能。