백준 1405: 미친 로봇 [C/C++]

https://www.acmicpc.net/problem/1405

1405번: 미친 로봇

#include <iostream>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
long double N, w[4]; // 동, 서, 남, 북
int visited[30][30]; // 방문 여부 확인
int dy[4] = {0, 0, 1, -1}; // 동서남북
int dx[4] = {1, -1, 0, 0}; // 동서남북
long double track(int y, int x, long double p, int cnt) {
    if (cnt == N or p == 0) return p; // 모두 이동 or 확률 0
    long double sum = 0; // 동서남북의 총 확률 계산
    for (int i = 0; i < 4; i++) {
        if (visited[y + dy[i]][x + dx[i]]) continue; // 이미 방문한 곳이면 넘어간다
        visited[y + dy[i]][x + dx[i]]++; // 방문했음
        sum += track(y + dy[i], x + dx[i], p * w[i], cnt + 1);
        visited[y + dy[i]][x + dx[i]]--; // 방문안함
    }
    return sum;
}
int main() {fastio();
    cin >> N >> w[0] >> w[1] >> w[2] >> w[3];
    for (int i = 0; i < 4; i++) w[i] /= 100; // 확률
    visited[15][15]++; // 중간에서 시작한다
    cout.precision(10); 
    cout << track(15, 15, 1, 0); // 중간에서 시작한다
    return 0;
}
 

00 : 13 : 56