Cleaning Robot - kyoupuro @ ウィキ

1020 : Cleaning Robot

問題文

解説

ロボットが移動した後に指定された場所にいるか確率を答える問題。
全探索しようとすると時間がかかりすぎるので、各部屋ごとにその部屋にいける場合の数をカウントする。

プログラム

C

C++

...

#include <iostream>
#include <cstdio>
using namespace std;
 
int main() {
    int n;
    char cs, ct, cb;
 
    while (cin >> n, n) {
        cin >> cs >> ct >> cb;
        int s = cs - 'A', t = ct - 'A', b = cb - 'A';
 
        int count[9] = {0};
        count[s] = 1;
 
        for (int i = 0; i < n; i++) {
            int plus[9] = {0};
            for (int j = 0; j < 9; j++) {
                // 上に移動             
                if (j-3 >= 0 && j-3 != b) {
                    plus[j-3] += count[j];
                } else {
                   plus[j] += count[j];
                 }
                // 下に移動             
                if (j+3 <= 8 && j+3 != b) {
                   plus[j+3] += count[j];
                } else {
                    plus[j] += count[j];
                }
                // 右に移動             
                if (j+1 <= 8 && j != 2 && j != 5 && j+1 != b) {
                    plus[j+1] += count[j];
                } else {
                    plus[j] += count[j];
                }
                // 左に移動             
                if (j-1 >= 0 && j != 3 && j != 6 && j-1 != b) {
                    plus[j-1] += count[j];
                } else {
                    plus[j] += count[j];
                }
            }
 
            for (int j = 0; j < 9; j++) {
                count[j] = plus[j];
            }
        }
 
        int sum = 1;
        for (int i = 0; i < n; i++) sum *= 4;
 
        cout << (double)count[t]/sum << endl;
    }
 
    return 0;
}

Java