Java递归实现带条件二维数组寻路：求到-1的最小步数

给定一个填充非负数的二维数组，其中存在一个值为-1的单元格。需要从arr[0][0]出发，返回到达-1的最小步数。移动规则如下：

• 数组元素视为屋顶高度，移动时的高度差分为“下降”和“攀爬”：从5到3是下降，差值为2；从1到2是攀爬，差值为-1。
• 若攀爬时差值小于-1（即攀爬高度超过1），或下降时差值大于2（即下降高度超过2），则该移动非法。
• 例外情况：若相邻单元格是目标-1，可直接移动，无需判断高度差。
• 若无有效路径则返回-1，有路径则返回最小步数。

示例数组：

[2,  0,  1,  2,  3]
[2,  3,  5,  5,  4]
[8,  5, -1,  8,  7]
[3,  4,  7,  2,  4]
[2,  4,  3,  1, -1]

原代码存在的问题 #

• 数组越界判断错误：j>drm[drm.length-1].length应为j >= drm[i].length（列索引从0开始，最大列索引为drm[i].length-1）。
• 目标判断逻辑错误：上下左右方向判断-1时，左侧和上方的条件误写为==1，正确应为==-1。
• 移动逻辑局限：仅尝试向右、向下的固定路径，未覆盖所有合法方向，也未处理路径回溯和最小步数的比较。
• 递归缺陷：未记录已访问单元格，会导致重复访问陷入死循环；无法多路径比较，无法返回最小步数。

求最小步数问题，**广度优先搜索（BFS）**是最优选择——BFS按层级遍历，第一次到达目标时的步数即为最小步数，相比递归DFS效率更高，天然适配最短路径需求。

核心步骤：

1. 初始化队列：存储当前坐标和已走步数，初始加入起点(0, 0, 0)。
2. 已访问标记：用二维布尔数组记录已访问位置，避免重复计算和死循环。
3. 队列遍历：每次取出队首元素，若当前位置是目标-1，直接返回步数。
4. 四方向合法性判断：对上下左右相邻位置依次检查：
   • 是否在数组边界内；
   • 是否未被访问；
   • 若相邻位置是-1，直接加入队列；
   • 若为普通数值，计算高度差，判断是否符合规则（下降差值≤2，攀爬差值≥-1），符合则标记访问并加入队列。
5. 无路径处理：队列遍历完毕未找到目标，返回-1。

import java.util.LinkedList;
import java.util.Queue;

public class MinStepsToTarget {
    // 四个移动方向：上、下、左、右
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static int findMinSteps(int[][] grid) {
        int rows = grid.length;
        if (rows == 0) return -1;
        int cols = grid[0].length;

        // 起点即为目标的特殊情况
        if (grid[0][0] == -1) return 0;

        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0}); // 存储[i, j, 当前步数]
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int i = current[0];
            int j = current[1];
            int steps = current[2];

            // 遍历四个移动方向
            for (int[] dir : DIRECTIONS) {
                int ni = i + dir[0];
                int nj = j + dir[1];

                // 边界与访问状态检查
                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && !visited[ni][nj]) {
                    // 找到目标，返回步数+1
                    if (grid[ni][nj] == -1) {
                        return steps + 1;
                    }

                    // 计算高度差，判断移动合法性
                    int heightDiff = grid[i][j] - grid[ni][nj];
                    // 下降：差值≥0且≤2；攀爬：差值≥-1且<0（即最多攀爬1格）
                    if ((heightDiff >= 0 && heightDiff <= 2) || (heightDiff >= -1 && heightDiff < 0)) {
                        visited[ni][nj] = true;
                        queue.add(new int[]{ni, nj, steps + 1});
                    }
                }
            }
        }

        // 无有效路径
        return -1;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {2, 0, 1, 2, 3},
                {2, 3, 5, 5, 4},
                {8, 5, -1, 8, 7},
                {3, 4, 7, 2, 4},
                {2, 4, 3, 1, -1}
        };
        System.out.println(findMinSteps(grid)); // 输出：5（从(0,0)到(2,2)的最小步数）
    }
}

代码说明 #

• 方向数组：统一管理四个移动方向，简化代码逻辑，避免重复编写上下左右判断。
• 已访问标记：彻底解决重复访问问题，提升效率并防止死循环。
• BFS特性：第一次遇到目标时返回的步数即为最小步数，无需后续路径比较。
• 逻辑分层：先判断边界和访问状态，再处理目标和移动合法性，逻辑清晰易维护。

内容的提问来源于stack exchange，提问作者Rami Mamadov