BOJ)1405 미친 로봇

문제: icpc.me/1405

각 방향으로 이동할 확률과 이동 횟수가 주어질 때 경로가 단순할 확률을 구하는 문제이다.

dfs를 통한 4방향 탐색으로 각 방향으로 이동할 확률을 곱해서 brute force 해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, visited[30][30];
double p[4];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
double dfs(int x, int y, int cnt) {
    if (cnt == 0)return 1.0;
    double ret = 0.0;
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (visited[cx][cy])continue;
        ret += dfs(cx, cy, cnt - 1)*p[i];
    }
    visited[x][y] = false;
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < 4; i++) {
        scanf("%lf", &p[i]);
        p[i] /= 100.0;
    }
    printf("%.9lf\n", dfs(15, 15, n));
    return 0;
}