题目
给定一个n*m的迷宫，如
S..
..#
E.E
其中，S代表开始位置，#代表不可行走的墙，E代表出口。
主人公从开始位置出发，每次等概率的随机选择下一个可以行走的位置(可能会发生回溯)，直到到达某一个出口为止。
现在他想知道，在这一概率事件中，它从开始位置走到某一个出口的期望步数是多少。
思路
1. 期望 E = p1 * step1 + p2 * step2 +... pn * stepn
2. 因为可能会发生回溯, 因此直接使用 dfs 并不靠谱
3. 那么考虑 dp[i][j], dp[i][j] 表示到达终点的期望, 是否可行呢? 在题目描述给出的例子中, dp[2][1] = 1/3*1 + 1/3*1 + dp[1][1]*1/3; 而 dp[1][1] = ... + dp[2][1]*1/3;
这就造成了死锁. 但机器学习似乎用过这个技术
4.
13年10月 月赛第一场 set 4 迷宫问题,布布扣,bubuko.com
原文：http://www.cnblogs.com/xinsheng/p/3575703.html