c++ 백준_1405_"미친 로봇"

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

1405번: 미친 로봇

N의 값이 작아

DFS를 돌렸다.

​

이동할 수 있는 board로 넓직하게 최대 14니까 30x30 board를 만들어 탐색했다.

​

그리고 입력된 확률을 100으로 나눠서

0.xx 형태로 바꾸고

그 방향으로 갈 때마다 곱해서

누적확률을 최종 도착지에서 더해주었다.

​

​

*

답은 잘 나오는데 답은 틀렸다고 나온다

​

소수점 출력 부분이 잘못된 거 같아

처음으로

cout.precision(n);

을 사용했다.

​

소수점을 n자리까지 표현하겠다는 뜻이다.

 

#include <iostream>
#include <vector>
using namespace std;

double total = 0;

vector<double> dir(4);

bool board[30][30];

void dfs(int x,int y,int N,double possible) {

	if (x < 0 || y < 0 || x >30 || y > 30 || board[x][y])
		return;


	if (N == 0) {
		total += possible;
		return;
	}
	board[x][y] = true;
	
	if (dir[0]){ // 동
		if(!board[x][y+1])
			dfs(x, y+1, N - 1, possible * dir[0]);
	}
	if (dir[1]) { // 서 
		if (!board[x][y - 1])
			dfs(x, y-1, N - 1, possible * dir[1]);
	}
	if (dir[2]) { // 남
		if (!board[x+1][y]) 
			dfs(x+1, y, N - 1, possible * dir[2]);
	}
	if (dir[3]) { // 북
		if (!board[x - 1][y])
			dfs(x-1, y, N - 1, possible * dir[3]);
	}
	board[x][y] = false;
}

int main(void) {
	
	int N;
	cin >> N;

	for (int i = 0; i < 4; i++) {
		cin >> dir[i];
		dir[i] /= 100;
	}

	dfs(15, 15, N , 1);
	cout.precision(16);
	cout << total;
}