AOJ 1020 Cleaning Robot
問題概要、制約
解法
確率DPをする。
dp[i][j] := バッテリーをi使って位置jにいるときの確率。
位置は二次元座標だが、(x, y)をy * 3 + xのようにすると次元を1つ落とすことができる。
コード
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; pii get_pos(int x) { return pii(x / 3, x % 3); } bool inField(int x, int y) { return (0 <= x && x < 3 && 0 <= y && y < 3); } int main() { int N; while (cin >> N, N) { string S = "ABCDEFGHI"; char a[3]; for (int i = 0; i < 3; i++) { cin >> a[i]; } int s = S.find(a[0]); int t = S.find(a[1]); int b = S.find(a[2]); double dp[25][9] = {{}}; pii p = get_pos(b); dp[0][s] = 1; const int di[] = {-1, +0, +1, +0}; const int dj[] = {+0, -1, +0, +1}; for (int i = 0; i < N; i++) { for (int j = 0; j < 9; j++) { if (dp[i][j] == 0) continue; pii n = get_pos(j); for (int k = 0; k < 4; k++) { int ni = n.first + di[k]; int nj = n.second + dj[k]; if (!inField(nj, ni) || (pii(ni, nj) == p)) { dp[i+1][j] += dp[i][j] / 4; } else { dp[i+1][ni*3+nj] += dp[i][j] / 4; } } } } printf("%.10f\n", dp[N][t]); } return 0; }