地下迷宮 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 <iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
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<node> q;
bool isok(int x,int y)//判斷是否越界
{
return x>=0&&x<n&&y>=0&&y>=0&&y<m&&maze[x][y]!='X';
}
void bfs()//寬搜。記錄可到達點
{
int nx,ny,i;
while(!q.empty())
q.pop();
cnt=0;
nx=st.x;
ny=st.y;
pp[nx][ny]=cnt++;
q.push(st);
while(!q.empty())
{
t=q.front();
q.pop();
for(i=0;i<4;i++)
{
nx=t.x+dx[i];
ny=t.y+dy[i];
if(isok(nx,ny)&&pp[nx][ny]==-1)
{
q.push(node(nx,ny));
pp[nx][ny]=cnt++;//對可到達點編號
}
}
}
}
bool guass()//高斯消元
{
int row,i,j,id;
double maxx,var;
for(row=0;row<cnt;row++)//遍歷行。重點在mat[row][row]先找此處最大系數。然後把以下方程的對應未知數消去
{
maxx=fabs(mat[row][row]);
id=row;//id記錄位置
for(i=row+1;i<cnt;i++)
{
if(fabs(mat[i][row])>maxx)
{
maxx=fabs(mat[i][row]);//注意是絕對值大
id=i;
}
}
if(maxx<eps)
return false;
if(id!=row)//如果就是當前處理行就不用交換
{
for(i=row;i<=cnt;i++)//交換最大行和當前行
swap(mat[row][i],mat[id][i]);
}
for(i=row+1;i<cnt;i++)//遍歷行。所以<cnt.把當前處理行以下的mat[row][row]變量消去。
{
if(fabs(mat[i][row])<eps)//本來就為0就不用處理了
continue;
var=mat[i][row]/mat[row][row];
for(j=row;j<=cnt;j++)//包括擴展矩陣所以c<=cnt。
mat[i][j]-=mat[row][j]*var;
}
}
for(i=cnt-1;i>=0;i--)//從最後一個系數開始
{
for(j=i+1;j<cnt;j++)
mat[i][cnt]-=mat[i][j]*mat[j][j];
mat[i][i]=mat[i][cnt]/mat[i][i];//現在系數矩陣的對角線用於記錄答案。
}
return true;
}
int main()
{
int i,j,k,nx,ny,p;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<n;i++)
{
scanf("%s",maze[i]);
for(j=0;j<m;j++)
{
if(maze[i][j]=='D')
st.x=i,st.y=j;
else if(maze[i][j]=='E')
ed.x=i,ed.y=j;
}
}
memset(pp,-1,sizeof pp);
bfs();
if(pp[ed.x][ed.y]==-1)
{
printf("tragedy!\n");
continue;
}
memset(mat,0,sizeof mat);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(pp[i][j]!=-1)//以每個可到達點建立方程組
{
ptr=0;
p=pp[i][j];
for(k=0;k<4;k++)
{
nx=i+dx[k];
ny=j+dy[k];
if(isok(nx,ny))
{
mat[p][pp[nx][ny]]=-1;
ptr++;
}
}
mat[p][p]=ptr;
mat[p][cnt]=ptr;
}
}
}
p=pp[ed.x][ed.y];
memset(mat[p],0,sizeof mat[p]);
mat[p][p]=1;//在終點步數的期望為0.
if(guass())
{
p=pp[st.x][st.y];
if(mat[p][p]<=1000000)
printf("%.2lf\n",mat[p][p]);
else
printf("tragedy!\n");
}
else
printf("tragedy!\n");
}
return 0;
}
