티스토리 뷰

알고리즘 관련/BOJ

BOJ)1405 미친 로봇

JASON 자손9319 2017. 6. 7. 18:38

문제: 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)1405 미친 로봇  (0) 2017.06.07
BOJ)10838 트리  (0) 2017.06.07
BOJ)14590 KUBC League (Small)  (0) 2017.06.06
BOJ)13538 XOR 쿼리  (0) 2017.06.05
댓글
댓글쓰기 폼