[골4] 1405 - 미친 로봇

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

#pragma region 상하좌우 / 위치

const pair<int, int> dir[]
{
	{  1,  0 },
	{ -1,  0 },
	{  0, -1 },
	{  0,  1 },
};

#define y first
#define x second

#pragma endregion

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

#define SIZE 4

double arrProb[SIZE];
double simple;
int n;

bool vis[100][100];

void DFS(int _y = 50, int _x = 50, double prob = 1.0f, int cnt = 0)
{
	// 겹치면 
	if (vis[_y][_x])
		return;

	vis[_y][_x] = true;

	if (cnt == n)
	{
		simple += prob;
		vis[_y][_x] = false;
		return;
	}
	// 동서남북 확인
	for (int i = 0; i < SIZE; i++)
	{
		int ny = _y + dir[i].y, nx = _x + dir[i].x;
		DFS(ny, nx, prob * arrProb[i], cnt + 1);
	}
	vis[_y][_x] = false;
}

int main()
{
	FAST_IO();

	cout << fixed;
	cout.precision(18);
	cin >> n;

	for (int i = 0; i < SIZE; i++)
	{
		double prob;
		cin >> prob;
		arrProb[i] = prob / 100.0f;
	}
	DFS();
	cout << simple;
	return 0;
}