Giả sử chúng ta có một bàn cờ NxN, một quân sĩ bắt đầu ở hàng thứ r và cột thứ c và cố gắng thực hiện đúng K nước đi. Ở đây, các hàng và cột được lập chỉ mục 0, vì vậy hình vuông trên cùng bên trái là (0, 0) và hình vuông dưới cùng bên phải là (N-1, N-1).
Một hiệp sĩ có thể di chuyển trong 8 ô khác nhau từ một ô, điều đó có thể được hiển thị trong sơ đồ này -
Mỗi khi kỵ sĩ di chuyển, nó sẽ chọn ngẫu nhiên một trong tám nước đi có thể có. Quân sĩ tiếp tục di chuyển cho đến khi nó thực hiện đúng K nước đi hoặc đã di chuyển khỏi bàn cờ. Chúng ta phải tìm xác suất để hiệp sĩ vẫn còn trên bàn cờ sau khi nó ngừng di chuyển.
Vì vậy, nếu đầu vào là 3, 2, 0, 0, thì đầu ra sẽ là 0,0625. Điều này là do có hai nước đi (đến (1,2), (2,1)) sẽ giữ quân sĩ trên bàn cờ. Bây giờ từ mỗi vị trí đó, cũng có hai nước đi sẽ giữ các hiệp sĩ trên bàn cờ. Vì vậy, ở đây tổng xác suất mà hiệp sĩ ở lại trên bàn cờ là 0,0625.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định dir mảng một hướng, điều này giống như [[-2, -1], [-2, 1], [2, -1], [2, 1], [1,2], [1, -2], [-1,2], [-1, -2]]
- Xác định phương thức đệ quy giải quyết (), điều này sẽ nhận x, y, n, k và mảng 3d dp
- nếu x> =n hoặc y> =n hoặc x <0 hoặc y <0, thì trả về 0
- nếu k bằng 0, thì trả về 1
- nếu dp [k, x, y] không phải là -1 thì trả về dp [k, x, y]
- dp [k, x, y]:=0
- cho tôi trong phạm vi từ 0 đến 7
- dp [k, x, y]:=giải quyết (x + dir [i, 0], y + dir [i, 1], n, k - 1, dp)
- trả về dp [k, x, y]
- Từ phương pháp chính, hãy thực hiện như sau
- tạo một mảng 3d có kích thước (k + 1) x N x N. Điền vào ô này với - 1
- trả về giải quyết (r, c, N, k, dp) / (8 ^ K)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
3 2 0 0
Đầu ra
0.0625