思考题 for nobody

# Rougelike Game

You are given a graph of N*M grids. Each grid can be a wall 'X',a path'.' or unknown '?'

One grid is the start point 'S' and one grid is the end point 'E'

Now we change the '?' randomly to 'X' or '.' and run shortest path from S to E. (4 directions walking)

What's the expected length of route from S to E if we ignore the unreachable situation.

If impossible, print -1.

Examples:

3 3

S..

.X.

??E

Output:

3

Explain:

Could be -

S..

.X.

..E 3

S..

.X.

.XE 3

S..

.X.

X.E 3

S..

.X.

XXE 3

Constriants:

Subtask 1(90%) 1<=n,m<=4

Subtask 2(10%) 1<=n,m<=1000

**Orange boy come and get AC quickly. Although this looks like an impossible problem**