알고리즘
백준 15488번 나이트가 체스판을 벗어나지 않을 확률 C++ (골드5)
영춘권의달인
2024. 6. 1. 11:06
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;
}