一个含有n个点的迷宫是一棵树，每个点都有一定的概率成为这个迷宫的入口和出口，从这个迷宫走出去的方法是从入口开始进行深度优先搜索，如果当前有多个移动方案，那么等概率的选择移动方案中的一个，DFS的过程为以下的伪代码：。random shuffle the vertices' order in V // here all permutations have equal probability to be chosen. V是与x点相邻的点的序列，Flag数组初始时是全部为FALSE的，DFS 初始时从入口开始，当搜索结束时，变量count将会统计移动的次数。
一个含有n个点的迷宫是一棵树（一个任意两点之间都恰好有一条路径的无向图）。每个点都有一定的概率成为这个迷宫的入口和出口。 从这个迷宫走出去的方法是从入口开始进行深度优先搜索。如果当前有多个移动方案，那么等概率的选择移动方案中的一个。DFS的过程为以下的伪代码： DFS(x) if x == exit vertex then finish search flag[x] < - TRUE random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen for i < - 1 to length[V] do if flag[V[i]] = FALSE then count++; DFS(y); count++; V(x)是与x点相邻的点的序列。Flag数组初始时是全部为FALSE的。DFS 初始时从入口开始。当搜索结束时，变量count将会统计移动的次数。 你的任务是统计一个人从这个迷宫的入口走到出口步数的数学期望值。 样例说明 入口总是1且出口有2/5的概率是2，3/5的概率是3。对于出口为2和3的数学期望是相同的（对称的情况），第一步有0.5的概率直接 到达出口，0.5的概率走错到另一个点（然后再走两步到终点）。所以数学期望等于2/5*(1*0.5+3*0.5)+3/5* (1*0.5+3*0.5) = 2。
（图片来源网络，侵删）
