-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathKnight.java
More file actions
120 lines (94 loc) · 3.25 KB
/
Copy pathKnight.java
File metadata and controls
120 lines (94 loc) · 3.25 KB
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
package chapter5;
import java.util.ArrayList;
import java.util.List;
/**
* 西洋骑士
*/
public class Knight {
private static int[][] DIRECTIONS = {{-2, 1}, {-1, 2}, {1, 2},{2, 1},{2, -1},{1, -2},{-1, -2},{-2, -1}};
private Map map;
private int[] directionCounts;
public void setMap(int size) {
map = new Map();
map.initMap(size);
directionCounts = new int[size];
}
public int[][] getMap() {
return map.getMap();
}
public boolean travel(int row, int col) {
//对应骑士可走的八个方向
List<Coordinate> nextCoordinate = new ArrayList<>();
int pos, tmp, directionCount;
Coordinate entry = new Coordinate(row, col);
map.setVal(entry, 1);
for(int step = 2; step <=64; step++) {
nextCoordinate.clear();
directionCount = 0;
for (int i = 0; i < 8; i++) {
directionCounts[i] = 0;
}
for (int[] direction : DIRECTIONS) {
Coordinate coordinate = map.getNextCoordinate(
row, col, direction[0], direction[1]);
if (coordinate == null) {
continue;
}
if (map.getVal(coordinate) == 0) {
nextCoordinate.add(coordinate);
directionCount++;
}
}
if (directionCount == 0) {
return false;
} else if (directionCount == 1) {
pos = 0;
} else {
//找出下一个位置的出路
for (int j=0; j < directionCount; j++) {
//试探八个方向
for (int[] direction : DIRECTIONS) {
Coordinate coordinate = map.getNextCoordinate(
nextCoordinate.get(j).getRow(), nextCoordinate.get(j).getCol(), direction[0], direction[1]);
if (coordinate == null) {
continue;
}
if (map.getVal(coordinate) == 0) {
directionCounts[j]++;
}
}
}
tmp = directionCounts[0];
pos = 0;
for (int k = 1;k<directionCount;k++) {
if (directionCounts[k]<tmp) {
tmp = directionCounts[k];
pos = k;
}
}
}
row = nextCoordinate.get(pos).getRow();
col = nextCoordinate.get(pos).getCol();
map.setVal(nextCoordinate.get(pos), step);
}
return true;
}
public static void main(String[] args) {
int startX = 3;
int startY = 4;
Knight knight = new Knight();
knight.setMap(8);
if(knight.travel(startX,startY)) {
System.out.println("Finished");
} else {
System.out.println("Failed");
}
int[][] result = knight.getMap();
for(int i=0; i<8; i++) {
for(int j=0; j<8; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println();
}
}
}