2014
03-02

# Teleport Out!

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.

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.

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.

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

1.000
2.000
6.000
3.250

//c++  #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define INF (1<<29)
#define eps (1e-5)
#define pb push_back
using namespace std;
/*
struct Edge{
int v,next,w;
}edge[MAXN*3];
int E,list[MAXN];
void init() {memset(list,E=-1,sizeof(list)); }
{
edge[++E].v=v; edge[E].w=w; edge[E].next=list[u]; list[u]=E;
}
*/
int input()
{
int a,k=1; char c;
while ( (c=getchar())>'9' || c<'0')
if (c=='-') k=-1;
a=c-'0';
while ( (c=getchar())<='9' && c>='0') a=a*10+c-'0';
return a*k;
}

struct node
{
int x,y,s;
};
node make_node(int x,int y,int s)
{
node a;
a.x=x; a.y=y; a.s=s;
return a;
}
queue<node> q;
#define MAXN 205
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
double f[MAXN][MAXN];
int n,m;
bool judge(int x,int y)
{
return !vis[x][y] && x>0 && x<=n && y>0 && y<=m && s[x][y]!='X' && s[x][y]!='E';
}

void bfs(int EX,int EY,double mid,int sum)
{
memset(vis,0,sizeof(vis));
while (q.size()) q.pop();
q.push( make_node(EX,EY,0) );
vis[EX][EY]=true;
while (q.size())
{
node now=q.front(); q.pop();
if (now.s>mid/sum+1)
f[now.x][now.y]=min(f[now.x][now.y],mid/sum+1);
else
f[now.x][now.y]=min(f[now.x][now.y],1.0*now.s);
rep(dx,-1,1)
rep(dy,-1,1)
if (dx*dy==0 && (dx||dy))
if (judge(now.x+dx,now.y+dy))
{
node tmp=make_node(now.x+dx,now.y+dy,now.s+1);
vis[tmp.x][tmp.y]=true;
q.push(tmp);
}
}
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while (scanf("%d%d",&n,&m) && (n||m))
{
rep(i,1,n) scanf("%s",&s[i][1]);
int sum=0,YX,YY;
rep(i,1,n) rep(j,1,m)
{
if (s[i][j]=='Y') YX=i,YY=j;
if (s[i][j]!='X') sum++;
}
double l,r,mid,ans;
l=0; r=n*m*n*m;
rep(ii,1,40)
{
mid=(l+r)/2;
double w=0;
rep(i,1,n) rep(j,1,m) f[i][j]=INF;
rep(i,1,n) rep(j,1,m) if (s[i][j]=='E') bfs(i,j,mid,sum);
rep(i,1,n) rep(j,1,m) if (s[i][j]!='X') f[i][j]=min(f[i][j],mid/sum+1) , w=w+f[i][j];
if (w<mid) r=mid ,ans=f[YX][YY];
else l=mid;
}
printf("%.3lf\n",ans);
}
//system("pause");
return 0;
}

1. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！