[DFS] BJ1405 미친 로봇

문제 출처: https://www.acmicpc.net/problem/1405

 

Solution

• 모든 경로 탐색하는 문제, DFS하면서 해당 경로 갈 확률을 더해하고, 이미 visit한 곳은 simple path가 아니기 때문에 제외한다.

Point

• DFS return할 때 다른 경로로 해당 칸 갈 경우도 고려해야하므로 visit을 false로 해줘야한다.
• 출력 양식을 문제 오차 범위 조건에 맞게 잘 해줘야 한다.

---

#include <iostream>
#include <cstring>

using namespace std;

int N;
double p[4]; //pe, pw, ps, pn
bool visited[30][30];
int dx[4] = { 1, -1, 0, 0 }; //E, W, S, N
int dy[4] = { 0, 0, -1, 1 };

void input() {
    cin >> N;
    for (int i = 0; i < 4; i++) {
        int x;
        cin >> x;
        p[i] = x / (double)100;
    }
}

double dfs(int cx, int cy, int depth) {
    if (depth == N) return 1.0;
    visited[cx][cy] = true;
    double result = 0.0;
    for (int i = 0; i < 4; i++) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if (visited[nx][ny]) continue;
        result += p[i] * dfs(nx, ny, depth+1);
    }
    visited[cx][cy] = false;
    return result;
}

int main()
{
    input();
    printf("%.10lf\n", dfs(14, 14, 0));
}