[残りのバッテリー][y座標][x座標]で確率のDP! 常に等確率なのでやりやすい。
#include <iostream> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) const int dx[] ={ 0,1,0,-1}; const int dy[] ={-1,0,1, 0}; int main(){ int n; while(cin >> n , n){ long double dp[16][5][5] = {{{0.0}}}; char map[5][5]; rep(i,5)rep(j,5)map[i][j] = 'X'; rep(i,3)rep(j,3)map[i+1][j+1] = ' '; int sx, sy, gx, gy, bx, by; char s,t,b; cin >> s >> t >> b ; sy = (s-'A')/3 +1 , sx = (s-'A')%3 +1; gy = (t-'A')/3 +1 , gx = (t-'A')%3 +1; by = (b-'A')/3 +1 , bx = (b-'A')%3 +1; map[by][bx] = 'X'; dp[n][sy][sx] = 1.0; while(n){ for(int y=1;y<=3;y++){ for(int x=1;x<=3;x++){ rep(i,4){ int tx = x+dx[i], ty = y+dy[i] ; if(map[ty][tx] == 'X')ty = y , tx = x; dp[n-1][ty][tx] += dp[n][y][x] / 4.0; } } } n--; } printf("%.8Lf\n",dp[0][gy][gx]); } }