1020:Cleaning Robot

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020&lang=jp

確率DP。
dp[使ったバッテリーの量][Y座標][X座標]:=確率

dp[k+1][y+dy[ i ] ][x+dx[ i ] ]+=dp[k][y][x]/4

もしその方向に動けない場合は

dp[k+1][y][x]+=dp[k][y][x]/4

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstdio>

#define X first
#define Y second

using namespace std;

typedef pair<int,int> P;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
string idx="ABCDEFGHI";

int main(void){
	
	map<char,P> mp;
	int cnt=0,b;
	
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)mp[idx[cnt++]]=P(i,j);
	
	P s,t,d;
	char S,T,D;
	while(cin >> b >> S >> T >> D){
		
		s.X=mp[S].X,s.Y=mp[S].Y;
		t.X=mp[T].X,t.Y=mp[T].Y;
		d.X=mp[D].X,d.Y=mp[D].Y;
		
		double dp[16][3][3];
		
		for(int i=0;i<16;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)dp[i][j][k]=0;
		
		dp[0][s.Y][s.X]=1;
		
		for(int k=0;k<b;k++){
			for(int x=0;x<3;x++){
				for(int y=0;y<3;y++){
					for(int i=0;i<4;i++){
						int nx=x+dx[i],ny=y+dy[i];
						if(nx<0 || ny<0 || 2<nx || 2<ny || (nx==d.X && ny==d.Y))nx=x,ny=y;
						dp[k+1][ny][nx]+=dp[k][y][x]/4;
					}
				}
			}
		}
		printf("%.8f\n",dp[b][t.Y][t.X]);
	}
	return 0;
}