-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKnight probability in chessboard
68 lines (44 loc) · 1.59 KB
/
Knight probability in chessboard
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
double knightProbability(int n, int k, int row, int column) {
vector < vector <double> > orginal(n , vector <double>(n , 0.0)) ;
orginal[row][column] = 1 ;
vector < vector <double> > duplicate(n , vector <double>(n , 0.0)) ;
//duplicate = orginal ;
int rowoffset[] = {-2,-2,-1,-1,2,2,1,1};
int coloffset[] = {1,-1,2,-2,1,-1,2,-2};
while(k != 0 )
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
if(orginal[i][j] != 0 )
{
for(int w = 0 ; w < 8 ; w++)
{
int xcor = i + rowoffset[w] ;
int ycor = j + coloffset[w] ;
if(xcor < n && xcor >=0 && ycor >= 0 && ycor < n )
{
duplicate[xcor][ycor] = duplicate[xcor][ycor] + (orginal[i][j]/8.0) ;
}
}
}
}
}
orginal = duplicate ;
fill(duplicate.begin(),duplicate.end(),vector<double>(n,0.0));
k = k - 1 ;
}
double tp = 0.0 ;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
tp = tp + orginal[i][j] ;
}
}
return tp ;
}
};