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

#include<iostream>
#define IO_SETTING cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
using namespace std;
int n;
int ny, nx;
double ans;
double pos[4]; // E W S N 확률 저장
bool check[30][30];
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0, 0};

void backtracking(int depth, int cy, int cx, int dir, double possible) {
	// base condiction
	if (check[cy][cx]) {
		cout << "복잡" << ans << endl;
		return; // 이동 경로가 복잡일 경우 확률 0
	}
	if (depth > n) {
		ans += possible;
		cout << ans << endl;
		return;
	}// 14번 이동했을 때 확률 반환
	// depth = 0일 때 넘기기
	if (depth != 0) {
		possible *= pos[dir];
		cout << "pos: " << possible << " ";
		check[cy][cx] = 1;
		cy = cy + dy[dir];
		cx = cx + dx[dir];
	}
	
	backtracking(depth + 1, cy, cx, 0, possible);
	
	backtracking(depth + 1, cy, cx, 1, possible);
	
	backtracking(depth + 1, cy, cx, 2, possible);
	
	backtracking(depth + 1, cy, cx, 3, possible);
	check[cy][cx] = 0;
}
int main(void) {
	IO_SETTING;

	cin >> n;
	for (int i = 0; i < 4; i++) {
		double p;
		cin >> p;
		pos[i] = p / 100;
	}
	backtracking(0, 15, 15, -1, 1);
	cout << ans;

}