JavaAlgorithms/KnightShortestPath.java at master · heliuphy/JavaAlgorithms · GitHub

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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}
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
importjava.util.LinkedList;
importjava.util.Queue;

classPoint {
intx;
inty;

Point() {
x = 0;
y = 0;
 }

Point(inta, intb) {
x = a;
y = b;
 }
}

publicclassKnightShortestPath {
/**
 * @param grid: a chessboard included 0 (false) and 1 (true)
 * @param source: a point
 * @param destination: a point
 * @return: the shortest path
 */
publicintshortestPath(boolean[][] grid, Pointsource, Pointdestination) {
// write your code here
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return0;
 }

intm = grid.length;
intn = grid[0].length;

int[][] moveArray = newint[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
 { -2, -1 } };

Queue<Point> q = newLinkedList<>();
q.offer(source);
intstep = 0;

if (source.x == destination.x && source.y == destination.y) {
return0;
 }

while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Pointp = q.poll();
for (intj = 0; j < 8; j++) {
PointnewPoint = newPoint(p.x + moveArray[j][0], p.y + moveArray[j][1]);
if (inBound(newPoint, m, n) && grid[newPoint.x][newPoint.y] == false) {
if (newPoint.x == destination.x && newPoint.y == destination.y) {
returnstep + 1;
 }
q.offer(newPoint);
grid[newPoint.x][newPoint.y] = true;
 } else {
continue;
 }
 }
 }
step++;
 }

return -1;

 }

privatebooleaninBound(Pointp, intm, intn) {
if (p.x < 0 || p.x >= n) {
returnfalse;
 }

if (p.y < 0 || p.y >= m) {
returnfalse;
 }

returntrue;
 }

publicstaticvoidmain(String[] args) {
KnightShortestPathk = newKnightShortestPath();
boolean[][] grid = newboolean[][] { { false, false, false }, { false, false, false },
 { false, false, false } };
Points = newPoint(2, 0);
Pointd = newPoint(2, 2);

System.out.println(k.shortestPath(grid, s, d));
 }
}