计算以最小化离开迷宫的预期步数,怎么才能采用C语言的程序的设计的代码的编写的过程的设计的实现的原理

Problem Description
You are in a rectangular maze and you would like to leave the maze as quickly as possible. The maze is a rectangular grid of square locations. Some locations are blocked. Some other locations are exits. If you arrive at an exit location, you can immediately leave the maze.

You may walk one step at a time, onto one of the locations adjacent to your current location. Two locations are adjacent if they share a side. That is, you can only move one step North, South, East or West. Of course, you cannot step off the maze, and you cannot step onto a blocked location.

In addition, at any step, you may choose to use your teleport device. This device will send you to a random non-blocked location inside the maze with uniform probability (including, possibly, the one where you currently are standing!). If the device happens to send you onto a spot that is also an exit, then you leave the maze immediately. Hooray!

The only way to leave the maze is by moving onto an exit (either by teleport or walking), you may not walk off the boundary of the maze. Write a program to calculate the expected number of steps you need in order to leave the maze. Assume that you would choose your actions (movements and using teleport device) optimally in order to minimize the expected number of steps to leave the maze. Using the teleport device is considered one step.

Input
There will be multiple test cases. Each test case starts with a line containing two positive integers R and C ( R<=200, C<=200 ). Then, the next R lines each contain C characters, representing the locations of the maze. The characters will be one of the following:

E
: represents an exit, there will be at least one E' in every maze.
Y
: represents your initial location, there will be exactly one
Y' in every maze.
X
: represents a blocked location.
.
: represents an empty space.

You may move/teleport onto any location that is marked E',Y' or `.'.

The end of input is marked by a line with two space-separated 0's.

Output
For each test case, print one line containing the minimum expected number of steps required to leave the maze, given that you make your choices optimally to minimize this value. Print your result to 3 decimal places. Do not print any blank lines between outputs.

Sample Input
2 1
E
Y
2 2
E.
.Y
3 3
EX.
XX.
..Y
3 3
EXY
.X.
...
0 0

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
QT 迷宫游戏 可视化迷宫
2
深度优先搜索,迷宫问题,边长大于7*7就运行不出来。
0
C++迷宫(栈实现),无法回溯
1
用java写的迷宫,能够打开自己制定的迷宫地图,并找出最短路径和遍历迷宫
1
骑士游历C语言版,用类似迷宫算法如下,求大神告知错误的地方。
2
c语言走迷宫问题提问!
0
这是我写的迷宫问题的代码,请问各位大神为什么最后输出不了迷宫通路呀
0
用Java做算法提高 学霸的迷宫
1
一个数据结构上面路径可达性判断的问题,要求采用C语言技术
0
一个迷宫是否联通的有效性的判定算法怎么实现,采用C语言编程怎么实现
0
蓝桥杯 测试提示运行错误怎么回事呢
0
迷宫的遍历的算法在数据结构方面的一个运用,怎么采用C程序的语言的技术设计的代码实现?
0
c语言,迷宫问题,救救孩子
2
为什么到最后一直无法输出迷宫路径?
0
迷宫的绕路的一个算法问题,如何运用C语言的程序的编写的方式实现
0
数组走到右上角时可以获得的最大金币数目,请问怎么样才能使用C语言的程序的编写的技术实现的?
0
一个迷宫的便利的典型的算法问题,怎么利用C语言程序代码思路解题的过程?
0
数字的迷宫的寻路的算法解决,怎么采用c程序的语言编写的技术实现的呢?
0
走到右上角时可以获得的最大金币数目的运算,怎么采用C程序的语言代码编写技术去实现的呢?
0
迷宫的寻找的路线的问题,要求使用C语言的程序的编写的设计的代码的过程的做法怎么才能实现的呢?