使用 BFS 查找网格上对象的可能路径数

我有一个代表网格的矩阵，并且想找出对象可以移动到的所有可能的位置。

物体只能水平或垂直移动。

假设下面的示例是我正在查看的网格，它表示为二维矩阵。对象是 *，0 是对象可以移动到的空白空间，1 是对象无法跳过或继续的墙壁。

如果该对象只能水平或垂直移动，找到该对象所有可能移动的最佳方法是什么？

我想打印一条消息：“该对象可以到达 9 个地方。” 9 用于下面的示例，但我希望它适用于以下网格的任何配置。所以我所要做的就是给出 * 的当前坐标，它将给出它可以移动到的可能位置的数量。

需要注意的是，计算中不考虑 * 的原始位置，这就是为什么在下面的示例中，消息将打印 9 而不是 10。

我有一个 isaWall 方法，可以告诉我单元格是否是墙。 isaWall 方法位于 Cell 类中。每个单元格都由其坐标表示。我研究过使用 BFS 或 DFS 等算法，但我不太明白在这种情况下如何实现它们，因为我对这些算法不太熟悉。我想过使用 Cells 作为图的节点，但不太确定如何遍历图，因为从我在网上看到的 BFS 和 DFS 的示例来看，通常会有一个目标节点和源节点（源是*) 的位置，但在这种情况下我实际上没有目标节点。我真的很感激一些帮助。

00111110
01000010
100*1100
10001000
11111000

编辑：我检查了评论中推荐的网站，并尝试实现我自己的版本。不幸的是它没有起作用。我知道我必须扩展“前沿”，我基本上只是将扩展代码翻译为Java，但它仍然不起作用。该网站继续解释该过程，但就我而言，没有可以转到的目标单元格。我真的很感激与我的案例有关的示例或更清晰的解释。

EDIT2：我仍然很困惑，有人可以帮忙吗？

虽然 BFS/DFS 常见used寻找起点和终点之间的联系，这实际上并不是它们的本质。 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;
        }
    }
}

细胞.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 递归地触及每个可到达的单元格once通过以下步骤：

1. 将当前单元格标记为已访问
2. 循环遍历每个相邻单元格
3. 如果该单元格尚未被访问过，则对该单元格进行 DFS，并将与该单元格相邻的单元格数量添加到当前计数中
4. 返回与当前单元格相邻的单元格数量 + 1

你可以看到这个的可视化here https://www.youtube.com/watch?v=tlPuVe5Otio。有了我们已经编写的所有辅助功能，这非常简单：

地图助手.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;
    }
}

就是这样！如果您需要有关代码的任何解释，请告诉我。