我有一個表示網格的矩陣，并想找出對象可以移動到的所有可能位置。一個物體只能水平或垂直移動。假設下面的示例是我正在查看的網格，它表示為 2d 矩陣。對象是 *，0 是對象可以移動到的空白空間，1 是對象不能跳過或繼續前進的墻壁。如果該對象只能水平或垂直移動，那么找到該對象所有可能移動的最佳方法是什么？我想打印一條消息說：“對象可以去 9 個地方?！?9 用于下面的示例，但我希望它適用于下面網格的任何配置。所以我所要做的就是給出 * 的當前坐標，它會給我它可以移動到的可能位置的數量。需要注意的是，計算中不考慮 * 的原始位置，這就是為什么對于下面的示例，消息將打印 9 而不是 10。我有一個 isaWall 方法，它告訴我單元格是否是墻。isaWall 方法位于 Cell 類中。每個單元格都由其坐標表示。我研究過使用 BFS 或 DFS 等算法，但我不太了解在這種情況下如何實現它們，因為我對算法不太熟悉。我想用 Cells 作為圖的節點，但不太確定如何遍歷圖，因為從我在網上看到的 BFS 和 DFS 的例子中，你通常會有一個目標節點和源節點（源是*) 的位置，但在這種情況下我并沒有真正的目標節點。我真的很感激一些幫助。0011111001000010100*11001000100011111000編輯：我檢查了評論中推薦的網站，并嘗試實現我自己的版本。不幸的是，它沒有用。我知道我必須擴展“邊界”并且我基本上只是將擴展代碼翻譯成Java，但它仍然不起作用。該網站繼續解釋該過程，但在我的情況下，沒有目標單元格可以去。我非常感謝與我的案例有關的示例或更清晰的解釋。EDIT2：我仍然對此感到很困惑，有人可以幫忙嗎？
1 回答
人到中年有點甜
TA貢獻1895條經驗 獲得超7個贊
雖然 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通過以下步驟遞歸地接觸每個可達單元一次：
將當前單元格標記為已訪問
循環遍歷每個相鄰的單元格
如果尚未訪問該單元格，則對該單元格進行 DFS，并將與該單元格相鄰的單元格數量添加到當前計數中
返回與當前單元格相鄰的單元格數 + 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;
}
}
就是這樣！如果您需要有關代碼的任何解釋，請告訴我。
添加回答
舉報
0/150
提交
取消