백준 1405번 미친 로봇 C++

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

 

백트래킹을 이용해서 마지막 이동까지 마쳤을 때 이동 경로가 단순한 로봇들이 지나온 길의 확률들만 모두 더하는 방식으로 문제를 해결하였다.

 

중간에 이미 방문한 곳을 가려고 하면 그곳은 탐색을 하지 않았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };
vector<vector<bool>> visited(30, vector<bool>(30, false));
vector<double> proV(4);
int n;
double ans = 0;

void BT(int cnt, int row, int col, double pro) {
	if (cnt >= n) {
		ans += pro;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nextRow = row + dRow[i];
		int nextCol = col + dCol[i];
		if (visited[nextRow][nextCol]) continue;
		visited[nextRow][nextCol] = true;
		BT(cnt + 1, nextRow, nextCol, pro * proV[i]);
		visited[nextRow][nextCol] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
		
	visited[15][15] = true;
	cin >> n;
	for (int i = 0; i < 4; i++) {
		cin >> proV[i];
		proV[i] /= 100;
	}
	BT(0, 15, 15, 1);
	cout.precision(20);
	cout << ans;
};