图是一个二维数组,请java 代码实现广度优先搜索 BFS,并给出详细代码以及最终输出结果

已解决

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] + ") "); // 打印路径中的每个点
        }
    }
}

}

展开
收起
f33qyvrkuj5as 2025-03-19 14:57:19 78 分享 版权
1 条回答
写回答
取消 提交回答
  • 通义灵码是基于通义大模型的 AI 研发辅助工具,提供代码生成、研发问答、任务执行等能力,为开发者带来智能化研发体验,引领 AI 原生研发新范式。通义灵码包含 AI 编码助手和 AI 程序员。 更多信息欢迎加入通义灵码用户交流群(钉钉群号53770000738)
    官方回答

    感谢您的使用和反馈,欢迎进通义灵码用户交流群,让小灵儿的技术哥哥们帮忙定位下问题吧~进群密码——钉钉群号🔍53770000738

    2025-03-25 14:47:13
    赞同 371 展开评论

基于通义大模型的 AI 编码辅助工具,支持代码智能生成、单元测试生成、问题排查、研发智能问答等功能,为开发者带来高效、流畅的编码体验。

热门讨论

热门文章

还有其他疑问?
咨询AI助理