백준 15488번 나이트가 체스판을 벗어나지 않을 확률 C++ (골드5)

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

 

dp테이블을 [행][열][움직일 수 있는 횟수]로 정하고 똑같은 행,열, 움직일 수 있는 횟수를 2번이상 탐색한다면 기존에 구해놓은 값을 바로 반환하는 메모이제이션 방식을 사용하였다.

 

나이트가 다음에 가있을 칸을 계산하고 움직일 수 있는 횟수를 1씩 줄이면서 탐색해나간다.

1. 만약 나이트가 체스판 밖에있다면 0을 반환한다.

2. 만약 나이트가 방문한 [행][열][움직일 수 있는 횟수] 가 이전에 탐색된 기록이 있다면 그 값을 바로 반환한다.

3. 만약 k가 0이면 더이상 움직일 수 없고, 체스판 안쪽에 있기 때문에 1을 반환한다.

 

나이트가 움직일 수 있는 방향은 8방향이기때문에 8방향에 대해 탐색을 진행한 값을 8로 나누고 캐시 테이블에 저장한 뒤 반환한다.

 

#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 <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int dRow[8] = { 2,1,-1,-2,-2,-1,1,2 };
int dCol[8] = { 1,2,2,1,-1,-2,-2,-1 };

int n;
vector<vector<vector<double>>> cache = vector<vector<vector<double>>>(51, vector<vector<double>>(51, vector<double>(51, -1)));

double dp(int r, int c, int k) {
    if (r <= 0 || r > n) return 0;
    if (c <= 0 || c > n) return 0;
    if (cache[r][c][k] != -1) return cache[r][c][k];
    if (k == 0)
    {
        return cache[r][c][k] = 1;
    }

    double& ret = cache[r][c][k];
    ret = 0;
    for (int i = 0; i < 8; i++)
    {
        int nextRow = r + dRow[i];
        int nextCol = c + dCol[i];
        ret += dp(nextRow, nextCol, k - 1);
    }
    return ret = ret / 8;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int x, y, k;
    cin >> n >> x >> y >> k;
    double ans = dp(x, y, k);

    cout << fixed;
    cout.precision(10);
    cout << ans;
}