Time Limit:1000MS Memory Limit:32768K

Description:

由于山体滑坡，DK被困在了地下蜘蛛王国迷宫。为了抢在DH之前来到TFT，DK必须尽快走出此迷宫。此迷宫仅有一个出口，而由于大BOSS的力量减弱影响到了DK，使DK的记忆力严重下降，他甚至无法记得他上一步做了什么。所以他只能每次等概率随机的选取一个方向走。当然他不会选取周围有障碍的地方走。如DK周围只有两处空地，则每个都有1/2的概率。现在要求他平均要走多少步可以走出此迷宫。

Input:

先是一行两个整数N, M(1<=N, M<=10)表示迷宫为N*M大小，然后是N行，每行M个字符，'.'表示是空地，'E’表示出口，'D’表示DK，'X’表示障碍。

Output:

如果DK无法走出或要超过1000000步才能走出，输出tragedy!，否则输出一个实数表示平均情况下DK要走几步可以走出迷宫，四舍五入到小数点后两位。

Sample Input:

1 2

ED

3 3

D.X

.X.

X.E

Sample Output:

1.00

tragedy!

Source:

DK

思路：

首先对地图节点重新标号。假设E[i]表示DK从i点开始走出迷宫的期望值。

那么E[i]=(E[a1]+E[a2]+E[a3]+...+E[an])/n+1，其中a1...an是i的相邻节点。

那么对于每一个DK可达的节点来说，都可以为它建立这样的一个方程。现

在假设DK可达的点有N个，那么我们最终将会得到N元一次方程组。方程成

环所以利用高斯消元解出E[No[S]]。其中S是DK的起点，No[S]是重标号后的

起点这里要重点注意的是，我们联立方程的时候，一定要注意DK可达这个条

件，不然就会导致无解的情况。貌似zjutoj崩了。不能交题了。代码仅供参考。

详细见代码：

#include   
#include  
#include  
#include  
#include  
using namespace std;  
const int maxn=15;  
const double eps=1e-9;  
char maze[maxn][maxn];//记录地图  
int pp[maxn][maxn];//重编号  
int dx[4]={0,0,-1,1};  
int dy[4]={1,-1,0,0};  
double mat[maxn][maxn];//记录矩阵  
int n,m,cnt,ptr;  
struct node  
{  
    int x,y;  
    node(int xx,int yy)  
    {  
        x=xx;  
        y=yy;  
    }  
    node(){}  
} st,ed,t;  
queue q;  
  
bool isok(int x,int y)//判断是否越界  
{  
    return x>=0&&x=0&&y>=0&&ymaxx)  
            {  
                maxx=fabs(mat[i][row]);//注意是绝对值大  
                id=i;  
            }  
        }  
        if(maxx=0;i--)//从最后一个系数开始  
    {  
        for(j=i+1;j