计算以最小化离开迷宫的预期步数,怎么才能采用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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问