博客

题目链接：http://cpp.zjut.edu.cn/ShowProblem.aspx?ShowID=1423

首先对地图节点重新标号。
假设E[i]表示DK从i点开始走出迷宫的期望值。那么E[i]=(E[a1]+E[a2]+E[a3]+...+E[an])/n+1，其中a1...an是i的相邻节点。
那么对于每一个DK可达的节点来说，都可以为它建立这样的一个方程。
现在假设DK可达的点有N个，那么我们最终将会得到N元一次方程组。最后利用高斯消元解出E[num[S]]。其中S是DK的起点，num[S]是重标号后的起点
这里要重点注意的是，我们联立方程的时候，一定要注意DK可达这个条件，不然就会导致无解的情况。

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#define exp 1e-12
using namespace std;
int equ,var;
double x[120];
double a[120][120];
int move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int num[120][120];
int n,m;
char map[15][15];
void debug()
{
    for(int i=0;i<equ;i++)
    {
        for(int j=0;j<=var;j++) printf("%3.2f ",a[i][j]);
        puts("");
    }
    puts("");
}
struct node
{
    int x,y;
}start,end;
void gauss()
{
    int i,j;
    int row,col;
    for(row=0,col=0;row<equ&&col<var;row++,col++)
    {
        int maxr=row;
        for(i=row+1;i<equ;i++) if( fabs(a[i][col])>fabs(a[maxr][col])) maxr=i;
        for(i=0;i<=var;i++) swap(a[row][i],a[maxr][i]);
        for(i=row+1;i<equ;i++)
        {
            if(fabs(a[i][col])>exp)
            {
                double ta=a[i][col]/a[row][col];
                for(j=col;j<=var;j++) a[i][j]-=a[row][j]*ta;
            }
        }
    }
    for(i=row-1;i>=0;i--)
    {
        double tep=a[i][var];
        for(j=i+1;j<var;j++)
        {
            if(fabs(a[i][j])<=exp) continue;
            tep-=a[i][j]*x[j];
        }
        x[i]=tep/a[i][i];
    }
}
int ok(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m) return 0;
    if(num[x][y]!=-1) return 0;
    if(map[x][y]=='X') return 0;
    return 1;
}
int bfs(int x,int y)
{
    int id=0;  //id为当前点重新编号后的编号
    node cur,next;
    cur.x=x;
    cur.y=y;
    end.x=-1;
    queue<node>q;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(num[cur.x][cur.y]!=-1) continue;  //注意去重
        num[cur.x][cur.y]=id++;
        if(map[cur.x][cur.y]=='D') start=cur;
        if(map[cur.x][cur.y]=='E') end=cur;

        for(int i=0;i<4;i++)
        {
            next.x=cur.x+move[i][0];
            next.y=cur.y+move[i][1];
            if(ok(next.x,next.y))
                q.push(next);
        }

    }

    if(end.x!=-1) return id;
    return -1;
}
int main()
{
    while(cin>>n>>m)
    {
        int i,j,k;
        for(i=0;i<n;i++) cin>>map[i];
        memset(num,-1,sizeof(num));
        memset(a,0,sizeof(a));
        int cont;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
                if(map[i][j]=='D') break;
            if(j!=m) break;
        }
        cont=bfs(i,j);   //cont返回可到达的点的数量
        if(cont==-1)     //无法走到 直接返回
        {
            puts("tragedy!");
            continue;
        }
        for(i=0;i<n;i++)   //每个点可到达的点与它建立期望关系 方程同题解给出 构造系数矩阵
        {
            for(j=0;j<m;j++)
            {
                if(num[i][j]==-1) continue;
                if(map[i][j]=='E')
                {
                    a[num[i][j]][num[i][j]]=1;
                    continue;
                }
                int cnt=0;
                for(k=0;k<4;k++)
                {
                    int xx=i+move[k][0];
                    int yy=j+move[k][1];
                    if(xx<0||yy<0||xx>=n||yy>=m||map[xx][yy]=='X') continue; //注意不能走要去掉。
                    cnt++;
                    a[num[i][j]][num[xx][yy]]=-1;
                }
                a[num[i][j]][num[i][j]]=a[num[i][j]][cont]=cnt;
            }
        }
        equ=var=cont;
        gauss();
        if(x[num[start.x][start.y]]>1000000) puts("tragedy!");
        else printf("%.2f\n",x[num[start.x][start.y]]);
    }
}