使用 BFS 查找网格上对象的可能路径数
Using BFS to find number of possible paths for an object on a grid
我有一个表示网格的矩阵,我想找出对象可以移动到的所有可能位置。
对象只能水平或垂直移动。
假设下面的示例是我正在查看的网格,它表示为二维矩阵。对象是*,0是对象可以移动到的空位,1是对象不能跳过或继续前进的墙。
如果该对象只能水平或垂直移动,那么找到该对象所有可能移动的最佳方法是什么?
我想打印一条消息说:"There are 9 places the object can go to." 9 用于下面的示例,但我希望它适用于下面网格的任何配置。所以我所要做的就是给出 * 的当前坐标,它会给我它可以移动到的可能位置的数量。
需要注意的是,* 的原始位置未在计算中考虑,这就是为什么对于下面的示例,消息将打印 9 而不是 10。
我有一个 isaWall 方法可以告诉我单元格是否是墙。 isaWall 方法在 Cell class 中。每个单元格都由其坐标表示。我研究了使用像 BFS 或 DFS 这样的算法,但我不太明白在这种情况下如何实现它们,因为我不太熟悉这些算法。我想过使用 Cells 作为图的节点,但不太确定如何遍历图,因为从我在网上看到的 BFS 和 DFS 示例来看,你通常会有一个目标节点和源节点(源是*) 的位置,但在这种情况下我并没有真正的目标节点。非常感谢您的帮助。
00111110
01000010
100*1100
10001000
11111000
编辑:我检查了评论中推荐的网站并尝试实现我自己的版本。不幸的是,它没有用。我知道我必须扩展 "frontier",我基本上只是将扩展代码翻译成 Java,但它仍然不起作用。该网站继续解释该过程,但就我而言,没有目的地单元可去。我非常感谢与我的案例有关的示例或更清晰的解释。
EDIT2:我仍然很困惑,有人可以帮忙吗?
虽然 BFS/DFS 通常 用于 查找起点和终点之间的联系,但实际上并非如此。 BFS/DFS 是 "graph traversal algorithms,",这是一种奇特的说法,他们发现从起点可以到达每个点。 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 通过以下步骤递归地接触每个可到达的单元格一次:
- 将当前单元格标记为已访问
- 遍历每个相邻单元格
- 如果该单元格尚未被访问过,则对该单元格进行DFS,并将与该单元格相邻的单元格数添加到当前计数中
- Return当前单元格相邻的单元格数+1
您可以看到这个 here 的可视化。使用我们已经编写的所有辅助功能,这非常简单:
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;
}
}
就是这样!如果您需要有关代码的任何解释,请告诉我。
我有一个表示网格的矩阵,我想找出对象可以移动到的所有可能位置。
对象只能水平或垂直移动。
假设下面的示例是我正在查看的网格,它表示为二维矩阵。对象是*,0是对象可以移动到的空位,1是对象不能跳过或继续前进的墙。
如果该对象只能水平或垂直移动,那么找到该对象所有可能移动的最佳方法是什么?
我想打印一条消息说:"There are 9 places the object can go to." 9 用于下面的示例,但我希望它适用于下面网格的任何配置。所以我所要做的就是给出 * 的当前坐标,它会给我它可以移动到的可能位置的数量。
需要注意的是,* 的原始位置未在计算中考虑,这就是为什么对于下面的示例,消息将打印 9 而不是 10。
我有一个 isaWall 方法可以告诉我单元格是否是墙。 isaWall 方法在 Cell class 中。每个单元格都由其坐标表示。我研究了使用像 BFS 或 DFS 这样的算法,但我不太明白在这种情况下如何实现它们,因为我不太熟悉这些算法。我想过使用 Cells 作为图的节点,但不太确定如何遍历图,因为从我在网上看到的 BFS 和 DFS 示例来看,你通常会有一个目标节点和源节点(源是*) 的位置,但在这种情况下我并没有真正的目标节点。非常感谢您的帮助。
00111110
01000010
100*1100
10001000
11111000
编辑:我检查了评论中推荐的网站并尝试实现我自己的版本。不幸的是,它没有用。我知道我必须扩展 "frontier",我基本上只是将扩展代码翻译成 Java,但它仍然不起作用。该网站继续解释该过程,但就我而言,没有目的地单元可去。我非常感谢与我的案例有关的示例或更清晰的解释。
EDIT2:我仍然很困惑,有人可以帮忙吗?
虽然 BFS/DFS 通常 用于 查找起点和终点之间的联系,但实际上并非如此。 BFS/DFS 是 "graph traversal algorithms,",这是一种奇特的说法,他们发现从起点可以到达每个点。 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 通过以下步骤递归地接触每个可到达的单元格一次:
- 将当前单元格标记为已访问
- 遍历每个相邻单元格
- 如果该单元格尚未被访问过,则对该单元格进行DFS,并将与该单元格相邻的单元格数添加到当前计数中
- Return当前单元格相邻的单元格数+1
您可以看到这个 here 的可视化。使用我们已经编写的所有辅助功能,这非常简单:
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;
}
}
就是这样!如果您需要有关代码的任何解释,请告诉我。