Использование BFS для определения количества возможных путей для объекта в сетке

Question

У меня есть матрица, представляющая сетку, и я хотел бы выяснить все возможные места, в которые может перемещаться объект.

Объект может двигаться только горизонтально или вертикально.

Предположим, чтоПример ниже - это сетка, на которую я смотрю, которая представлена ​​в виде 2-мерной матрицы.Объект - это *, 0 - это пустые места, в которые объект может двигаться, а 1 - это стены, через которые объект не может перепрыгнуть или перейти.

Каков наилучший способ найти все возможные движенияэтого объекта при условии, что он может двигаться только горизонтально или вертикально?

Я хотел бы напечатать сообщение, говорящее: «Есть 9 мест, куда может пойти объект».9 для примера ниже, но я хотел бы, чтобы он работал для любой конфигурации сетки ниже.Поэтому все, что мне нужно сделать, это дать текущие координаты *, и это даст мне количество возможных позиций, на которые он может переместиться.

Следует отметить, что исходная позиция * не считаетсяв вычислениях, поэтому в приведенном ниже примере сообщение будет печатать 9, а не 10.

У меня есть метод isaWall, который сообщает мне, является ли ячейка стеной или нет.Метод isaWall находится в классе Cell.Каждая ячейка представлена ​​своими координатами.Я изучал использование таких алгоритмов, как BFS или DFS, но я не совсем понимал, как реализовать их в этом случае, так как я не слишком знаком с алгоритмами.Я думал об использовании ячеек в качестве узлов графа, но не был слишком уверен, как пройти по графу, потому что из примеров, которые я видел в Интернете о BFS и DFS, вы обычно имели бы целевой узел и исходный узел (источником являетсяположение *), но в этом случае у меня нет узла назначения.Я был бы очень признателен за помощь.

00111110
01000010
100*1100
10001000
11111000

РЕДАКТИРОВАТЬ: я проверил веб-сайт, который был рекомендован в комментариях и попытался реализовать свою собственную версию.К сожалению, это не сработало.Я понимаю, что мне нужно расширить «границу», и я просто перевел код расширения на Java, но он все еще не работает.Веб-сайт продолжает объяснять процесс, но в моем случае нет целевой ячейки для перехода.Я был бы очень признателен за пример или более четкое объяснение, относящееся к моему делу.

РЕДАКТИРОВАТЬ2: Я до сих пор смущен этим, может кто-нибудь, пожалуйста, помогите?

Answer 1

Хотя BFS / DFS обычно используются для поиска связей между начальной и конечной точкой, на самом деле это не то, чем они являются.BFS / DFS - это «алгоритмы обхода графа», которые представляют собой причудливый способ сказать, что они находят каждую точку, достижимую с начальной точки.DFS (поиск в глубину вначале) проще в реализации, поэтому мы будем использовать его для ваших нужд (примечание: BFS используется, когда вам нужно найти расстояние до любой точки от начальной точки, а DFS используется, когда вам нужно толькочтобы перейти к каждой точке).

Я не знаю точно, как структурированы ваши данные, но я предполагаю, что ваша карта представляет собой массив целых чисел, и определю некоторые основные функции (для простоты я началячейка 2):

Map.java

import java.awt.*;

public class Map {
    public final int width;
    public final int height;

    private final Cell[][] cells;
    private final Move[] moves;
    private Point startPoint;

    public Map(int[][] mapData) {
        this.width = mapData[0].length;
        this.height = mapData.length;

        cells = new Cell[height][width];
        // define valid movements
        moves = new Move[]{
            new Move(1, 0),
            new Move(-1, 0),
            new Move(0, 1),
            new Move(0, -1)
        };

        generateCells(mapData);
    }

    public Point getStartPoint() {
        return startPoint;
    }

    public void setStartPoint(Point p) {
        if (!isValidLocation(p)) throw new IllegalArgumentException("Invalid point");

        startPoint.setLocation(p);
    }

    public Cell getStartCell() {
        return getCellAtPoint(getStartPoint());
    }

    public Cell getCellAtPoint(Point p) {
        if (!isValidLocation(p)) throw new IllegalArgumentException("Invalid point");

        return cells[p.y][p.x];
    }

    private void generateCells(int[][] mapData) {
        boolean foundStart = false;
        for (int i = 0; i < mapData.length; i++) {
            for (int j = 0; j < mapData[i].length; j++) {
                /*
                0 = empty space
                1 = wall
                2 = starting point
                 */
                if (mapData[i][j] == 2) {
                    if (foundStart) throw new IllegalArgumentException("Cannot have more than one start position");

                    foundStart = true;
                    startPoint = new Point(j, i);
                } else if (mapData[i][j] != 0 && mapData[i][j] != 1) {
                    throw new IllegalArgumentException("Map input data must contain only 0, 1, 2");
                }
                cells[i][j] = new Cell(j, i, mapData[i][j] == 1);
            }
        }

        if (!foundStart) throw new IllegalArgumentException("No start point in map data");
        // Add all cells adjacencies based on up, down, left, right movement
        generateAdj();
    }

    private void generateAdj() {
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[i].length; j++) {
                for (Move move : moves) {
                    Point p2 = new Point(j + move.getX(), i + move.getY());
                    if (isValidLocation(p2)) {
                        cells[i][j].addAdjCell(cells[p2.y][p2.x]);
                    }
                }
            }
        }
    }

    private boolean isValidLocation(Point p) {
        if (p == null) throw new IllegalArgumentException("Point cannot be null");

        return (p.x >= 0 && p.y >= 0) && (p.y < cells.length && p.x < cells[p.y].length);
    }

    private class Move {
        private int x;
        private int y;

        public Move(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

Cell.java

import java.util.LinkedList;

public class Cell {
    public final int x;
    public final int y;
    public final boolean isWall;
    private final LinkedList<Cell> adjCells;

    public Cell(int x, int y, boolean isWall) {
        if (x < 0 || y < 0) throw new IllegalArgumentException("x, y must be greater than 0");

        this.x = x;
        this.y = y;
        this.isWall = isWall;

        adjCells = new LinkedList<>();
    }

    public void addAdjCell(Cell c) {
        if (c == null) throw new IllegalArgumentException("Cell cannot be null");

        adjCells.add(c);
    }

    public LinkedList<Cell> getAdjCells() {
        return adjCells;
    }
}

Теперьнапишите нашу функцию DFS.DFS рекурсивно касается каждой достижимой ячейки один раз , выполняя следующие шаги:

1. Пометить текущую ячейку как посещенную
2. Цикл каждой соседней ячейки
3. Если ячейка еще не была посещена, добавьте в DFS эту ячейку и добавьте число ячеек, смежных с этой ячейкой, к текущему подсчету
4. Возвращает число ячеек, смежных с текущей ячейкой + 1

Вы можете увидеть визуализацию этого здесь .Со всеми функциями помощника, которые мы уже написали, все довольно просто:

MapHelper.java

class MapHelper {
    public static int countReachableCells(Map map) {
        if (map == null) throw new IllegalArgumentException("Arguments cannot be null");
        boolean[][] visited = new boolean[map.height][map.width];

        // subtract one to exclude starting point
        return dfs(map.getStartCell(), visited) - 1;
    }

    private static int dfs(Cell currentCell, boolean[][] visited) {
        visited[currentCell.y][currentCell.x] = true;
        int touchedCells = 0;

        for (Cell adjCell : currentCell.getAdjCells()) {
            if (!adjCell.isWall && !visited[adjCell.y][adjCell.x]) {
                touchedCells += dfs(adjCell, visited);
            }
        }

        return ++touchedCells;
    }
}

И это все!Дайте мне знать, если вам нужны пояснения по коду.