1405번

1405번 - 미친 로봇

처음에 문제를 제대로 안 읽고, 단순하지 않은 경로를 구하다 보니 시간초과가 발생했다.

근데 단순한 경로를 구하니까, 시간초과 없이 AC를 받았다.

나는 그냥 N제한이 최대 14이기 때문에, 60x60 의 충분히 큰 맵을 만들었다.

그리고 그냥 25,25를 시작으로 움직이도록 설정하였다. 그래서 다음에 방문할 지점이 한번도 방문하지 않은 곳

일때만 로봇이 움직이도록 구현했다.

<정답 코드>

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int n;
int MAX_N = 60;
double E, W, S, D;
double ans = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void dfs(int x,int y,int c,int e,int w,int s,int d,vector<vector<int>> &map)
{
    if (c == n)
    {
        double sum = 1;
 
        if (e != 0)
        {
            sum *= pow(E, e);
        }
        if (w != 0)
        {
            sum *= pow(W, w);
        }
        if (s != 0)
        {
            sum *= pow(S, s);
        }
        if (d != 0)
        {
            sum *= pow(D, d);
        }
 
        ans += sum;
        return;
    }
 
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];
        
        if (map[nx][ny] == 0)
        {
            map[nx][ny] += 1;
            if (k == 0)
            {
                dfs(nx, ny, c + 1, e + 1, w, s, d, map);
            }
            else if (k == 1)
            {
                dfs(nx, ny, c + 1, e, w + 1, s, d, map);
            }
            else if (k == 2)
            {
                dfs(nx, ny, c + 1, e, w, s + 1, d, map);
            }
            else if (k == 3)
            {
                dfs(nx, ny, c + 1, e, w, s, d + 1, map);
            }
            map[nx][ny] -= 1;
        }
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> E >> W >> S >> D;
    vector<vector<int>> map(MAX_N, vector<int>(MAX_N, 0));
    E /= 100;
    W /= 100;
    S /= 100;
    D /= 100;
 
    map[25][25] = 1;
    dfs(25,25,0,0,0,0,0,map);
 
    cout << ans << "\n";
 
    return 0;
}