1405 미친 로봇

#include <iostream>

using namespace std;

bool space[29][29] = {false,};
double probability[4];

int directionX[4] = {1, -1, 0, 0};
int directionY[4] = {0, 0, -1, 1};

int moveCount;

double dfs(int x, int y, int moveCount)
{
    int nextX;
    int nextY;
    
    if (moveCount == 0) {
        return 1.0;
    }

    space[x][y] = true;
    double result = 0.0;

    for (int i = 0; i < 4; i++){
        nextX = x + directionX[i];
        nextY = y + directionY[i];

        if (space[nextX][nextY] == true) {
            continue;
        }
        result += probability[i] * dfs(nextX, nextY, moveCount - 1);
    }
    space[x][y] = false;

    return result;
}

void solve()
{
    double result = dfs(14, 14, moveCount);

    cout << fixed;
    cout.precision(10);
    cout << result << endl;
}

void input()
{
    ios::sync_with_stdio(false);
    cin >> moveCount >> probability[0] >> probability[1] >> probability[2] >> probability[3];

    for (int i = 0; i < 4; i++) {
        probability[i] /= 100.0;
    }
}

int main(void)
{
    input();
    solve();
    
    return 0;
}

dfs로 풀었다.

처음에는 동 서 남 북 진짜 그 확률대로 움직이게 하려고 switch문을 쓰는 등 별의 별짓을 다 했다.

조금만 더 생각해보니 그냥 밟아보지 않은 방향으로의 확률만 계속 곱해주면 되어서 살짝 허무했기도 했다.

근데 정답은 계속 틀렸는데 아마 소숫점 오차(문제에서 10^-9까지 허용한다고 써있음) 때문인걸로 추측된다.

그래서 별 기믹을 추가하니 맞기는 맞았다.

살짝 찝찝해서 한번 더 살펴봐야겠다.