java 在一个二维数组中,B表示不能通过,K表示可以通过,终点为T,找出所有能走到T的起点
时间: 2023-09-21 14:06:20 浏览: 81
java 将一个二维数组存到txt文件里,然后再读取
5星 · 资源好评率100%
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决这个问题。
首先,我们需要定义一个二维数组来表示地图,并初始化它。在搜索过程中,我们需要记录每个点是否被访问过,可以使用一个布尔类型的二维数组来记录。我们还需要记录所有能够到达终点的起点,可以使用一个列表来存储。
接下来,我们可以从每个起点开始进行深度优先搜索或广度优先搜索。对于每个点,如果它是终点,就将该起点加入到列表中。否则,如果该点可达且未被访问过,则继续搜索。
具体实现可以参考以下代码:
```java
import java.util.ArrayList;
import java.util.List;
public class FindStartingPoints {
private static final int ROW = 5;
private static final int COL = 5;
private static char[][] map = {
{'B', 'B', 'B', 'B', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'K', 'B', 'K', 'B'},
{'B', 'B', 'B', 'B', 'T'}
};
private static boolean[][] visited = new boolean[ROW][COL];
private static List<int[]> startingPoints = new ArrayList<>();
public static void main(String[] args) {
// 遍历所有起点
for (int i = 1; i < ROW - 1; i++) {
for (int j = 1; j < COL - 1; j++) {
if (map[i][j] == 'K') {
dfs(i, j);
}
}
}
// 输出所有能到达终点的起点
System.out.println("Starting points:");
for (int[] point : startingPoints) {
System.out.println("(" + point[0] + ", " + point[1] + ")");
}
}
private static void dfs(int row, int col) {
visited[row][col] = true;
if (map[row][col] == 'T') {
startingPoints.add(new int[]{row, col});
return;
}
if (map[row + 1][col] == 'K' && !visited[row + 1][col]) {
dfs(row + 1, col);
}
if (map[row - 1][col] == 'K' && !visited[row - 1][col]) {
dfs(row - 1, col);
}
if (map[row][col + 1] == 'K' && !visited[row][col + 1]) {
dfs(row, col + 1);
}
if (map[row][col - 1] == 'K' && !visited[row][col - 1]) {
dfs(row, col - 1);
}
visited[row][col] = false;
}
}
```
上述代码使用深度优先搜索来遍历所有起点,对于每个起点,如果它可达终点,则将其加入到列表中。注意需要在搜索结束后将访问记录清除,以便处理下一个起点。
如果要使用广度优先搜索,可以使用队列来存储待访问的点,并在每一层结束后将访问记录清除。
阅读全文