-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKnight_Probability_In_Chessboard.java
130 lines (126 loc) · 3.91 KB
/
Knight_Probability_In_Chessboard.java
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Solution {
public boolean valid(int ni,int nj,int n)
{
if((ni<n && ni >=0) && (nj<n && nj>=0))
{
return true;
}
return false;
}
public double knightProbability(int n, int k, int row, int column) {
double curr[][]=new double[n][n];
double next[][]=new double[n][n];
curr[row][column]=1;
for(int mo=1;mo<=k;mo++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if (curr[i][j] !=0)
{
int ni=0;
int nj=0;
ni=i-2;
nj=j+1;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i-1;
nj=j+2;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i+1;
nj=j+2;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i+2;
nj=j+1;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i+2;
nj=j-1;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i+1;
nj=j-2;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i-1;
nj=j-2;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
ni=i-2;
nj=j-1;
if (valid(ni,nj,n))
{
next[ni][nj] += curr[i][j]/8.0;
}
}
}
}
curr=next;
next=new double[n][n];
}
double sum=0.0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
sum += curr[i][j];
}
}
return sum;
}
}
/* SHORT VERSION
class Solution {
public boolean valid(int ni, int nj, int n) {
return (ni < n && ni >= 0) && (nj < n && nj >= 0);
}
public double knightProbability(int n, int k, int row, int column) {
double curr[][] = new double[n][n];
double next[][] = new double[n][n];
curr[row][column] = 1;
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
for (int mo = 1; mo <= k; mo++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (curr[i][j] != 0) {
for (int move = 0; move < 8; move++) {
int ni = i + dx[move];
int nj = j + dy[move];
if (valid(ni, nj, n)) {
next[ni][nj] += curr[i][j] / 8.0;
}
}
}
}
}
curr = next;
next = new double[n][n];
}
double sum = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum += curr[i][j];
}
}
return sum;
}
}
*/