Я бы не пойти на библиотеку третьей стороны, потому что реализация алгоритма там будет сильно зависеть на пути изображен график (есть много вариантов , как двухмерный массив, список списков или какой-либо другой пользовательский класс). Если бы я был вами, я бы сам реализовал алгоритм.
Во-первых, вам необходимо определить структуру/класс, который будет представлять вашу доску с шарами, которые занимают некоторые из ячеек. Чтобы это было просто, я буду использовать двумерный массив пользовательского класса Cell, который я добавил как static. Он будет удерживать текущее состояние платы ('B' означает синий и 'O' обозначает orange).
Тогда мне понадобится метод, который возвращает все смежные ячейки для данной ячейки. Я буду использовать список смежных ячеек в реализации Depth First Search.
Наконец, реализация Depth-First Search будет работать следующим образом:
- Добавим стартовую ячейку в списке посещенных клеток.
- Мы находим все соседние ячейки исходной ячейки (чтобы узнать, к чему мы можем перейти).
- Для каждого из соседней ячейки, мы проверяем, если ячейка еще не посетили и не занята
- Если соседняя
cell не является ни посещала, ни занимала, мы делаем рекурсивный вызов dfs(cell, end).
- Мы останавливаемся, когда начальная ячейка совпадает с той, которую мы хотим достичь.
Вот реализация:
public class BoardOfBalls {
static class Cell {
private int x;
private int y;
private String value;
public Cell(int x, int y, String value) {
this.x = x;
this.y = y;
this.value = value;
}
}
private Cell[][] board;
private List<Cell> visited = new ArrayList<Cell>();
public void setBoard(Cell[][] board) {
this.board = board;
}
public List<Cell> getAdjacentCellsOf(Cell cell) {
List<Cell> result = new ArrayList<Cell>();
int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
for (int l = 0; l < 4 /* moves.length */; ++l) {
int ti = cell.x + moves[l][0];
int tj = cell.y + moves[l][1];
if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) {
result.add(board[ti][tj]);
}
}
return result;
}
public void dfs(Cell start, Cell end) {
visited.add(start);
if (start.x == end.x && start.y == end.y) {
printPath();
} else {
List<Cell> adjacent = getAdjacentCellsOf(start);
for (Cell cell : adjacent) {
if (!visited.contains(cell) && cell.value == null) {
dfs(cell, end);
}
}
}
}
private void printPath() {
System.out.print("Found a way: ");
for (int i = 0; i < visited.size(); i++) {
Cell next = visited.get(i);
System.out.print("[" + next.x + "][" + next.y + "]");
if (i != visited.size() - 1) {
System.out.print(" -> ");
}
}
System.out.println();
}
}
Я также написал простой main метод, который проверяет выполнение на меньшем борту:
public static void main(String[] args) {
Cell[][] cells = new Cell[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cells[i][j] = new Cell(i, j, null);
}
}
cells[0][2].value = "O";
cells[1][1].value = "B";
cells[2][2].value = "B";
BoardOfBalls board = new BoardOfBalls();
board.setBoard(cells);
board.dfs(cells[0][0], cells[2][1]);
}
, который печатает:
Found a way: [0][0] -> [1][0] -> [2][0] -> [2][1]
Должно быть несколько библиотек. У вас есть googled? – user1822729