하나의 NxN 체스판이 있고 기사가 r번째 행과 c번째 열에서 시작하여 정확히 K개의 이동을 시도한다고 가정합니다. 여기에서 행과 열의 인덱스는 0이므로 왼쪽 위의 정사각형은 (0, 0)이고 오른쪽 아래의 정사각형은 (N-1, N-1)입니다.
기사는 이 다이어그램에서 볼 수 있는 세포에서 8개의 다른 세포로 이동할 수 있습니다 -
기사가 이동할 때마다 8가지 가능한 이동 중 하나를 무작위로 선택합니다. 기사는 정확히 K개의 이동을 하거나 체스판에서 이동할 때까지 계속 이동합니다. 기사가 이동을 멈춘 후에도 보드에 남아 있을 확률을 찾아야 합니다.
따라서 입력이 3, 2, 0, 0과 같으면 출력은 0.0625가 됩니다. 이것은 기사를 보드에 유지하는 두 가지 이동((1,2), (2,1)으로)이 있기 때문입니다. 이제 각 위치에서 기사를 보드에 유지하는 두 가지 동작이 있습니다. 따라서 여기서 기사가 보드에 머무를 총 확률은 0.0625입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- [[-2,-1], [-2, 1],[2,-1], [2, 1], [1,2], [1, -2], [-1,2], [-1,-2]]
- 재귀적 방법 solve()를 정의합니다. x, y, n, k 및 3차원 배열 dp를 사용합니다.
- x>=n 또는 y>=n 또는 x <0 또는 y <0이면 0을 반환합니다.
- k가 0이면 1을 반환
- dp[k,x,y]가 -1이 아니면 dp[k,x,y]를 반환
- dp[k, x, y] :=0
- 0에서 7 사이의 i에 대해
- dp[k,x,y] :=solve(x+dir[i,0], y + dir[i, 1], n, k – 1, dp)
- dp[k,x,y]를 반환
- 메인 방법에서 다음을 수행합니다.
- 크기 (k + 1) x N x N의 3차원 배열을 만듭니다. – 1로 채웁니다.
- return solve(r, c, N, k, dp) / (8^K)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
class Solution {
public:
double solve(int x, int y, int n, int k, vector < vector < vector < double > > >& dp){
if(x >= n || y >= n || x < 0 || y < 0 ) return 0.0;
if(k == 0) return 1.0;
if(dp[k][x][y] != -1) return dp[k][x][y];
dp[k][x][y] = 0;
for(int i = 0; i < 8; i++){
dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp);
}
return dp[k][x][y];
}
double knightProbability(int N, int K, int r, int c) {
vector < vector < vector < double > > > dp (K + 1, vector < vector < double > >(N, vector < double >(N, -1))) ;
return solve(r, c, N, K, dp) / pow(8, K);
}
};
main(){
Solution ob;
cout << (ob.knightProbability(3, 2, 0, 0));
} 입력
3 2 0 0
출력
0.0625