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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
| public class Point {
public int X;
public int Y;
public Point(int X,int Y)
{
this.X=X;
this.Y=Y;
}
}
public class PathNode extends Point {
public Point goal;
public Point position;
public PathNode(Point point, PathNode pathNode, Point goal) {
super(point.X, point.Y);
position = point;
setCameFrome(pathNode);
this.goal = goal;
if (pathNode!=null)//нужно только для стартовой точки
setLengthFromStart(pathNode.getLengthFromStart());
else setLengthFromStart(-1);
setLengthToGoal(goal);
setFullLength(getLengthFromStart()+getLengthToGoal());
}
public PathNode CameFrome;//родительская точка
public void setCameFrome(PathNode CameFrome) {
this.CameFrome = CameFrome;
}
public int LengthFromStart;
public void setLengthFromStart(int i) {
LengthFromStart = i + 1;
}
public int getLengthFromStart() {
return LengthFromStart;
}
public int LengthToGoal;
public void setLengthToGoal(Point goal)//манхэттенское расстояние до цели
{
LengthToGoal = Math.abs(goal.X - this.position.X) + Math.abs(goal.Y - this.position.Y);
}
public int getLengthToGoal()
{
return LengthToGoal;
}
public int FullLength;
public void setFullLength(int i)
{
this.FullLength=i;
}
public int getFullLength() {
return FullLength;
}
}
public class newSolution {
public static char[][] matrix;
public static void main(String[] args) throws IOException{
matrix = creatFile(args[0]);//читает файл и создает матрицу.
Point start = new Point(0,0);
Point goal = new Point(600,600);
ArrayList<Point> list = FindPath(start,goal);
for (Point point : list)
{
System.out.print(point.X + " " + point.Y + " , ");
}
System.out.println();
System.out.println(list.size()-1);
//FileWriter outFile = new FileWriter("C:\\Users\\������������\\IdeaProjects\\���������\\src\\PAth\\2A");
// outFile.write(list.size());
}
public static char[][] creatFile(String fileName) throws IOException { //читает файл и создает матрицу.
BufferedReader inFile = new BufferedReader(new FileReader(fileName));
String[] size = inFile.readLine().split(" ");//из первой строки считывает размерность матрицы
int size1 = Integer.parseInt(size[0]);
int size2 = Integer.parseInt(size[1]);
System.out.println(size1 + " " + size2);
char[][] matr = new char[size1][size2];
String s;
for (int i = 0; i<size1; i++) {
s = inFile.readLine();
matr[i]=s.toCharArray();
}
inFile.close();
System.out.println();
return matr;
}
public static ArrayList<Point> FindPath(Point start, Point goal)
{
ArrayList<PathNode> closedSet = new ArrayList<>();//список рассмотренных точек
ArrayList<PathNode> openSet = new ArrayList<>();//список еще не рассмотренных точек
PathNode startNode = new PathNode(start,null,goal);
startNode.LengthFromStart=0;
int z=0;
openSet.add(startNode);
while (openSet.size() > 0)
{
PathNode currentNode = minLength(openSet);//находит точку с min "Полным путем"
if (currentNode.position.X == goal.X && currentNode.position.Y == goal.Y)
return GetPath(currentNode);//если в конечной точке, то возращает весь путь
closedSet.add(currentNode);
openSet.remove(currentNode);
for (PathNode neighbourNode : GetNeighbours(currentNode, goal))//рассматривает соседей текущей точки
{
if (CountInList(closedSet,neighbourNode)>0)//проверяет есть ли точка с этими координатами в closedSet
continue;//если да, то берем следующию
PathNode openNode = getInList(openSet, neighbourNode);//ищет точку с такими же координатами в openSet
if (openNode == null) {//если нет, то добавляет
openSet.add(neighbourNode);
} else {//если есть то проверяет не большее ли у нее путь от старта, чем у соседа текущей точки
if (openNode.LengthFromStart > neighbourNode.LengthFromStart) {
//если больше то заменяем ее данные на данные соседа
openNode.setCameFrome(currentNode);
openNode.LengthFromStart = neighbourNode.LengthFromStart;
openNode.FullLength = neighbourNode.FullLength;
}
}
}
}
return null;
}
private static ArrayList<PathNode> GetNeighbours(PathNode pathNode, Point goal)//возвращает список "годных" соседей
{
ArrayList<PathNode> result = new ArrayList<>();
Point[] neighbourPoints = new Point[4];
neighbourPoints[0] = new Point(pathNode.position.X + 1, pathNode.position.Y);
neighbourPoints[1] = new Point(pathNode.position.X - 1, pathNode.position.Y);
neighbourPoints[2] = new Point(pathNode.position.X, pathNode.position.Y + 1);
neighbourPoints[3] = new Point(pathNode.position.X, pathNode.position.Y - 1);
for(Point point : neighbourPoints)
{
if (point.X < 0 || point.X >= matrix.length)
continue;
if (point.Y < 0 || point.Y >= matrix[0].length)
continue;
if (matrix[point.X][point.Y] == '^')
continue;
PathNode neighbourNode = new PathNode(point,pathNode,goal);
result.add(neighbourNode);
}
return result;
}
public static int CountInList (ArrayList<PathNode> list, PathNode pathNode)//проверяет есть ли точка с этими координатами в closedSet
{
for (PathNode point : list)
{
if (point.position.X == pathNode.position.X && point.position.Y==pathNode.position.Y)
{
return 1;
}
}
return 0;
}
public static PathNode getInList (ArrayList<PathNode> list,PathNode pathNode)//ищет точку с такими же координатами в openSet
{
for (PathNode point : list)
{
if (point.position.X == pathNode.position.X && point.position.Y==pathNode.position.Y) {
return point;
}
}
return null;
}
public static ArrayList<Point> GetPath (PathNode pathNode)//возвращает список точек до данной.
{
ArrayList<Point> result = new ArrayList<>();
PathNode current = pathNode;
while (current!=null)
{
result.add(new Point(current.X,current.Y));
current = current.CameFrome;
}
return result;
}
public static PathNode minLength (ArrayList<PathNode> set)//находит точку с min "Полным путем"
{
PathNode result = set.get(0);
for (PathNode min : set)
{
if (min.FullLength<result.getFullLength())
{
result = min;
}
}
return result;
}
} |
(
