SRM 440 Div1 Medium MazeWandering

問題概要

nxmマスのグリッドで表される迷路がある。
'X'のマスは壁で、'.'のマスは通路、'*'のマスはチーズの置かれたマスである。
迷路は上下左右に隣合う、壁以外のマスへ移動できる。

この迷路は、チーズが必ず一つだけ置かれていることが保証されており、任意の通行可能な2つのマスについて、最短のパスが1通りに定まる。

この迷路をネズミが、上下左右で移動可能なマスのうち一つにランダムで移動することを繰り返す。このとき、チーズのマスまでたどり着くまでの期待値を全てのマスについて求め、その平均値を答えよ。

制約条件

迷路の高さ、幅≦50

方針

迷路は、マスを頂点、移動可能な関係を辺としたグラフとみると、条件から木になっていることがわかる。
木の根をチーズのマスとして考える。

任意のマスについて、期待値は
E(自分)=1+E(親)+E(子1)+E(子2)…のような形で表せることがわかる。
葉のノードについてはE(自分)=1+E(親)が成り立つので、
順々に変形していけば、E(自分)=a * E(親) + bの形にできることがわかる。

具体的にa,bの値を求めてやることで、それぞれのマスの期待値が求まる。

方針は思いつきやすいのだが実装は大変。
迷路のままでなく、一度グラフの形にしてやることで実装が少し楽になるかも。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w,N,num[50][50],sy,sx;
vs M;
vector<vi> e;

void makeGraph(int y,int x,int py,int px){
	rep(d,4){
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||nx<0||ny>=h||nx>=w||
			M[ny][nx]=='X'||ny==py&&nx==px
		)continue;
		e[num[y][x]].pb(num[ny][nx]);
		makeGraph(ny,nx,y,x);
	}
}

double a[2000],b[2000],sum;
void rec(int c){
	//e_c = a * e_parent + bの式を求める
	//cがrootならa=b=0
	//cがleafならa=b=1
	
	rep(i,e[c].size())rec(e[c][i]);
	if(c==num[sy][sx]){
		a[c]=b[c]=0;
	}
	else if(e[c].size()==0){
		a[c]=b[c]=1;
	}
	else{
		int deg=e[c].size()+1;
		double A=1.0/deg, B=0, C=1;
		rep(i,e[c].size())B+=a[e[c][i]]/deg, C+=b[e[c][i]]/deg;
		a[c]=A/(1-B); b[c]=C/(1-B);
	}
}
void rec2(int c,double ep){
	//親の期待値から自分の期待値を算出
	sum+=a[c]*ep+b[c];
	rep(i,e[c].size())rec2(e[c][i],a[c]*ep+b[c]);
}

class MazeWandering {
	public:
	double expectedTime(vector <string> maze) 
	{
		M=maze;
		h=M.size(), w=M[0].size();
		N=0;
		rep(i,h)rep(j,w)if(M[i][j]!='X'){
			num[i][j]=N++;
			if(M[i][j]=='*')sy=i, sx=j;
		}
		e.clear(); e.resize(N);
		makeGraph(sy,sx,sy,sx);
		
		rec(num[sy][sx]);
		sum=0;
		rec2(num[sy][sx],0);
		
		return sum/N;
	}
}