8000 Реализован волновой алгоритм · PromathBul/Wave_algorithm@6b36aff · GitHub
[go: up one dir, main page]
Skip to content

Commit 6b36aff

Browse files
PromathBulPromathBul
committed
Реализован волновой алгоритм
0 parents  commit 6b36aff

File tree

3 files changed

+157
-0
lines changed

3 files changed

+157
-0
lines changed

‎README.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# Реализация волнового алгоритма
2+
1. Создаем двумерный массив. Присваиваем элементам по краям массива значение -1.
3+
2. Создаем в середине массива блоки, через которые необходимо пройти. Для этого генерируем N случайных пар координат, и присваиваем этим элементам также значение -1.
4+
3. Начальную и конечную точку сперва можно определить как `[array.length - 2, 1]` и `[1, array.length - 2]`. Элементу `[array.length - 2, 1, 1]` присваиваем значение 1. Элементу `[1, array.length - 2]` - значение - 2, чтобы отличать его от остальных.
5+
4. Первая часть алгоритма заключается в присвоении соседним (справа, слева, снизу, сверху) элементам значение на 1 большее, чем у элемента-родителя. Для этого организовываем цикл по всему массиву, чтобы обнаружить элементы с текущим значением шагов. Элементам-соседям присваиваем значение на единицу больше, если их значение равно 0.
6+
5. Эту процедуру повторяем в цикле. Цикл продолжается пока не найден финишный элемент со значением -2 или не заполнен весь массив (не заменены все 0 на количество шагов).
7+
6. Вторая часть алгоритма заключается в поиске наикратчашего пути. Для этого ищем вокруг финишного элемента значение количества итераций, которое получем из прошлого метода заполнения массива. Каждую итерацию изменяем адрес ячейки и уменьшаем переменную, храняющую количество итераций, необходимых для достижения финишной ячейки. А также записываем в строку эти координаты.
8+
7. Полученная на выходе строка сожержит путь в обратном направлении. Поэтому с помощью `split` получаем массив строк, переворачиваем его, и отобращаем в консоле.
9+
10+
# К доработке
11+
1. Доработать вывод самого поля в консоль. В случае прямоугольной матрицы границы ячеек не рисуются пока.
12+
2. Обработать вариант, когда путь к финишу невозможен. Да данный момент программа вылетает с ошибкой.
13+
3. Написать ввод пользователя размера поля, количества стен.
14+
4. Организовать метод генерирования уникальных индексов для "установки" стен. На данный момент нет гарантии, что будет столько же стен, сколько указано в качестве аргумента в методе.
15+
5. Прописать условие максимального количества стен. Оно не может быть больше, чем количество нулей в исходном массиве.
16+
6. Визуализировать путь на отображаемом заполненном массиве, скажем, обозначив значения элементом другим цветом.
17+
7. Распределить более граммотно методы и всю структуру проекта. Организовать отдельно файл UI и, возможно, раздеить общие методы, специфические для этой задачи методы, и написанные в будущем методы проверок.

‎methods.java

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
import java.util.Scanner;
2+
import java.util.Random;
3+
4+
public class methods {
5+
static int inputNum(String msg) {
6+
Scanner iScanner = new Scanner(System.in);
7+
System.out.print(msg);
8+
int num = iScanner.nextInt();
9+
iScanner.close();
10+
return num;
11+
}
12+
13+
static int[][] createField(int rows, int columns) {
14+
int[][] field = new int[rows + 2][columns + 2];
15+
16+
for (int i = 0; i < field.length; i++) {
17+
for (int j = 0; j < field[i].length; j++) {
18+
if (i == 0 || i == rows + 1 || j == 0 || j == columns + 1)
19+
field[i][j] = -1;
20+
}
21+
}
22+
return field;
23+
}
24+
25+
static void show2dArray(int[][] array) {
26+
for (int i = 0; i < array.length * 8; i++) {
27+
System.out.print("_");
28+
}
29+
System.out.println();
30+
for (int i = 0; i < array.length; i++) {
31+
for (int j = 0; j < array[i].length; j++) {
32+
if (j != array[i].length - 1)
33+
System.out.printf("| %d\t", array[i][j]);
34+
else
35+
System.out.printf("| %d\t|", array[i][j]);
36+
}
37+
System.out.println();
38+
for (int k = 0; k < array.length * 8 + 1; k++) {
39+
if (k % 8 == 0)
40+
System.out.print("|");
41+
else
42+
System.out.print("_");
43+
}
44+
System.out.println();
45+
}
46+
}
47+
48+
static void buildingWalls(int[][] array, int walls) {
49+
Random rnd = new Random();
50+
for (int i = 0; i < walls; i++) {
51+
int row = rnd.nextInt(1, array.length - 1);
52+
int column = rnd.nextInt(1, array[0].length - 1);
53+
array[row][column] = -1;
54+
}
55+
}
56+
57+
static int drawRoutes(int[][] array) {
58+
int step = 1;
59+
for (; step < array.length * array[0].length - 2 * (array.length + array[0].length - 2); step++) {
60+
for (int i = 1; i < array.length - 1; i++) {
61+
for (int j = 1; j < array[i].length - 1; j++) {
62+
if (array[i][j] == step) {
63+
if (array[i + 1][j] == -2 || array[i - 1][j] == -2 || array[i][j + 1] == -2
64+
|| array[i][j - 1] == -2)
65+
return step;
66+
else {
67+
if (array[i - 1][j] == 0)
68+
array[i - 1][j] = step + 1;
69+
if (array[i + 1][j] == 0)
70+
array[i + 1][j] = step + 1;
71+
if (array[i][j + 1] == 0)
72+
array[i][j + 1] = step + 1;
73+
if (array[i][j - 1] == 0)
74+
array[i][j - 1] = step + 1;
75+
}
76+
}
77+
}
78+
}
79+
}
80+
return step;
81+
}
82+
83+
static String writeRoute(int[][] array, int[] finish, int step) {
84+
String route = String.format("(%d;%d) ", finish[0], finish[1]);
85+
for (int i = 0, value = A3DB step; i < step; i++, value--) {
86+
if (array[finish[0]][finish[1] - 1] == value)
87+
finish[1]--;
88+
else if (array[finish[0]][finish[1] + 1] == value)
89+
finish[1]++;
90+
else if (array[finish[0] + 1][finish[1]] == value)
91+
finish[0]++;
92+
else
93+
finish[0]--;
94+
route += String.format("(%d;%d) ", finish[0], finish[1]);
95+
}
96+
return route;
97+
}
98+
99+
static void ReverseArray(String[] array){
100+
for (int i = 0; i < array.length / 2; i++) {
101+
String helper = array[i];
102+
array[i] = array[array.length - 1 - i];
103+
array[array.length - 1 - i] = helper;
104+
}
105+
}
106+
107+
static void showArray(String[] array){
108+
for (int i = 0; i < array.length; i++) {
109+
System.out.print(array[i] + " ");
110+
}
111+
System.out.println();
112+
}
113+
114+
}

‎program.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
2+
public class program {
3+
public static void main(String[] args) {
4+
int[][] field = methods.createField(6, 6);
5+
methods.buildingWalls(field, 5);
6+
7+
// int[] start = new int[] { field.length - 2, 1 };
8+
int[] finish = new int[] { 1, field[0].length - 2 };
9+
10+
field[field.length - 2][1] = 1;
11+
field[1][field[0].length - 2] = -2;
12+
methods.show2dArray(field);
13+
14+
int step = methods.drawRoutes(field);
15+
System.out.println();
16+
methods.show2dArray(field);
17+
18+
String reversedRoute = methods.writeRoute(field, finish, step);
19+
20+
String[] reversedRouteArray = reversedRoute.split(" ");
21+
methods.ReverseArray(reversedRouteArray);
22+
System.out.println();
23+
methods.showArray(reversedRouteArray);
24+
}
25+
26+
}

0 commit comments

Comments
 (0)
0