본문 바로가기

알고리즘 관련/BOJ

BOJ)1405 미친 로봇

문제: icpc.me/1405


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
using namespace std;
int n, visited[30][30];
double p[4];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,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(1515, n));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)7154 Job Postings  (0) 2017.06.08
BOJ)12995 트리나라  (1) 2017.06.08
BOJ)10838 트리  (0) 2017.06.07
BOJ)14590 KUBC League (Small)  (0) 2017.06.06
BOJ)13538 XOR 쿼리  (0) 2017.06.05