<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)

### 전체탐색 ###

### SRM425 Div2 Level2 ###

<소스코드>

#include <vector>
using namespace std;
 
int visited[50][50];
int dr[]={0, 0, 1, -1};
int dc[]={1, -1, 0, 0}; // E W S N
int stack[20];
 
class CrazyBot {
public:
    int n;
    int dir[4];
    double ans;
    void dfs(int cnt, int r, int c) {
        if(cnt == n) {
            double tmp=1.0;
            for(int i=0; i<n; i++) {
                tmp *= (double)dir[stack[i]]/100;
            }
            ans += tmp;
            return ;
        }
        visited[r][c] = 1; 
        
        for(int k=0; k<4; k++) {
            int nr = r+dr[k];
            int nc = c+dc[k];
            if(!visited[nr][nc]) {
                stack[cnt] = k;
                dfs(cnt+1, nr, nc);
            }
        }
        visited[r][c] = 0; 
    }
 
    double getProbability(int n, int east, int west, int south, int north) {
        this->n = n;
        dir[0] = east; dir[1] = west;
        dir[2] = south; dir[3] = north;
        ans = 0;
        dfs(0, 25, 25); 
        return ans;
    }
};
 

>> n의 최대값이 14이므로 50x50 개의 판을 가정하고 그의 가운데인 (25,25)에서 로봇이 이동하기 시작한다고 생각하였다.

>> 성공적으로 보행할 확률은 이동할 수 있는 모든 경우의 수에 해당하는 확룰을 더하면 된다.