import java.util.*;
public class BFSGridExample {
// 定义方向数组,表示上下左右四个方向
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 广度优先搜索算法
public static List<int[]> bfs(int[][] grid, int startX, int startY, int goalX, int goalY) {
int rows = grid.length; // 获取网格的行数
int cols = grid[0].length; // 获取网格的列数
boolean[][] visited = new boolean[rows][cols]; // 创建一个访问标记数组
Queue<int[]> queue = new LinkedList<>(); // 创建一个队列用于BFS
Map<int[], int[]> parentMap = new HashMap<>(); // 创建一个父节点映射用于路径重建
queue.add(new int[]{startX, startY}); // 将起点加入队列
visited[startX][startY] = true; // 标记起点为已访问
parentMap.put(new int[]{startX, startY}, null); // 将起点的父节点设为null
while (!queue.isEmpty()) { // 当队列不为空时,继续搜索
int[] current = queue.poll(); // 从队列中取出当前节点
if (current[0] == goalX && current[1] == goalY) { // 如果当前节点是终点
return reconstructPath(parentMap, new int[]{startX, startY}, new int[]{goalX, goalY}); // 重建路径并返回
}
for (int[] direction : DIRECTIONS) { // 遍历四个方向
int newX = current[0] + direction[0]; // 计算新节点的x坐标
int newY = current[1] + direction[1]; // 计算新节点的y坐标
if (isValid(grid, newX, newY, visited)) { // 如果新节点有效
queue.add(new int[]{newX, newY}); // 将新节点加入队列
visited[newX][newY] = true; // 标记新节点为已访问
parentMap.put(new int[]{newX, newY}, current); // 记录新节点的父节点
}
}
}
return Collections.emptyList(); // 如果没有找到路径,返回空列表
}
// 检查坐标是否有效
private static boolean isValid(int[][] grid, int x, int y, boolean[][] visited) {
int rows = grid.length; // 获取网格的行数
int cols = grid[0].length; // 获取网格的列数
return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0 && !visited[x][y]; // 检查坐标是否在网格范围内、是否为可通行路径且未被访问
}
// 从父节点映射中重建路径
private static List<int[]> reconstructPath(Map<int[], int[]> parentMap, int[] start, int[] goal) {
List<int[]> path = new ArrayList<>(); // 创建一个路径列表
for (int[] at = goal; at != null; at = parentMap.get(at)) { // 从终点开始,沿着父节点映射回起点
path.add(at); // 将当前节点加入路径列表
}
Collections.reverse(path); // 反转路径列表,使其从起点到终点
return path; // 返回路径列表
}
public static void main(String[] args) {
int[][] grid = { // 定义一个网格
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
int startX = 0; // 起点的x坐标
int startY = 0; // 起点的y坐标
int goalX = 4; // 终点的x坐标
int goalY = 4; // 终点的y坐标
List<int[]> path = bfs(grid, startX, startY, goalX, goalY); // 调用BFS算法找到最短路径
if (path.isEmpty()) { // 如果路径为空
System.out.println("No path found from (" + startX + ", " + startY + ") to (" + goalX + ", " + goalY + ")"); // 输出未找到路径
} else {
System.out.print("Shortest path from (" + startX + ", " + startY + ") to (" + goalX + ", " + goalY + "): "); // 输出路径
for (int[] point : path) {
System.out.print("(" + point[0] + ", " + point[1] + ") "); // 打印路径中的每个点
}
}
}
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
感谢您的使用和反馈,欢迎进通义灵码用户交流群,让小灵儿的技术哥哥们帮忙定位下问题吧~进群密码——钉钉群号🔍53770000738