백준 문제 1405번 미친 로봇 문제풀이 c++

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

1405번: 미친 로봇

 

문제해석

 

이 문제에서 바로 확인한것이 N의 범위이다.

N의 최대값은 최대 14이므로 백트래킹으로 구현해도 약 3^14이면 충분히 시간초과는 안난다.

 

확률을 순서대로 동서남북의 순서로 배열에 담고 dy dx역시 동서남북 순서로 넣었다.

그리고 지나온길을 visited배열로 마킹하고 마킹이 되지않은쪽으로 깊이 n까지 도달하는 모든경우의 확률을 더해서 출력하면 답이된다.

 

시작하자마자 서쪽 또는 북쪽으로 가는경우 0,0에서 시작점으로 하면 인덱스 범위를 넘으므로 14,14를 시작점으로 했다

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
void dfs(int cx,int cy,int depth,long double csum);
bool visited[30][30];
long double percentage[4];
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int n;
long double ans=0;
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cout<<fixed;
    cout.precision(9);
    cin>>n;
    for(int i=0; i<4; i++)
    {
        cin>>percentage[i];
        percentage[i]=percentage[i]/100;
    }
    visited[14][14]=1;
    dfs(14,14,0,1);
    cout<<ans;
}
void dfs(int cx,int cy,int depth,long double csum){
    if(depth==n)
    {
        ans=ans+csum;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int nx=cx+dx[i];
        int ny=cy+dy[i];
        long double nsum=csum*percentage[i];
        if(visited[nx][ny]==0)
        {
            visited[nx][ny]=1;
            dfs(nx,ny,depth+1,nsum);
            visited[nx][ny]=0;
        }
    }
}