九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1546-九度Online Judge,用代码记录你的成长之路!

题目1546:迷宫问题

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:299

解决:40

题目描述:

给定一个n*m的迷宫,如
S..
..#
E.E
其中,S代表开始位置,#代表不可行走的墙,E代表出口。
主人公从开始位置出发,每次等概率的随机选择下一个可以行走的位置,直到到达某一个出口为止。
现在他想知道,在这一概率事件中,它从开始位置走到某一个出口的期望步数是多少。

输入:

输入包含多组测试用例,每组测试用例由两个整数n,m(1<=n,m<=15)开始,代表迷宫的大小
接下去n行每行m个字符描述迷宫信息,具体规则如题面所述。
数据保证至少存在一个E和一个S,但可能存在多个E。

输出:

输出一个浮点数,表示他走出迷宫的期望步数,保留两位小数。若主人公不可能走出迷宫,输出-1。

样例输入:
1 2
SE
2 2
S.
.E
1 3
S#E
样例输出:
1.00
4.00
-1
提示:

 走到.之后会有几率往回走。