思考题 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