Java二维数组两点间最长路径递归代码遇栈溢出，求修复方案

你的代码出现StackOverflowError主要是访问标记失效和递归逻辑错误导致的无限递归，以下是具体修复步骤：

问题核心分析 #

• 访问标记判断失效：LinkedList<Integer[]> visited中用contains判断节点是否已访问，但每次新建的Integer[]是不同对象，contains基于引用比较永远返回false，导致递归反复访问同一节点，栈溢出。
• 递归逻辑错误：
  1. 最长路径应该取所有分支中的最大值，而非累加所有分支长度；
  2. 回溯时未移除当前节点的访问标记，导致其他分支无法复用已访问节点。
• 顺序问题：终点判断放在邻居遍历之后，若当前节点是t，会先执行无效的邻居遍历。

修复后的完整代码 #

import java.util.*;

public class LongestPathFinder {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[][] park = new String[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                park[i][j] = sc.next();
            }
        }
        sc.close();

        int startX = 0, startY = 0;
        // 定位起点s的坐标
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (park[i][j].equals("s")) {
                    startY = i;
                    startX = j;
                    break;
                }
            }
        }

        // 改用二维数组记录访问状态，效率更高且判断准确
        boolean[][] visited = new boolean[n][n];
        visited[startY][startX] = true;
        int result = finding(park, startX, startY, visited);
        // 无有效路径时返回-1，否则返回路径节点数
        System.out.println(result == 0 ? -1 : result);
    }

    public static int finding(String[][] park, int x, int y, boolean[][] visited) {
        int n = park.length;
        // 优先判断是否到达终点
        if (park[y][x].equals("t")) {
            return 1;
        }

        int maxLength = 0;
        // 四个方向偏移量：右、左、下、上
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            // 检查坐标合法、未访问、不是障碍物$
            if (isValid(newX, newY, n, park) && !visited[newY][newX]) {
                visited[newY][newX] = true;
                // 递归获取当前分支的路径长度
                int currentLength = finding(park, newX, newY, visited);
                // 更新最长路径长度
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }
                // 回溯：取消当前节点的访问标记，允许其他分支访问
                visited[newY][newX] = false;
            }
        }

        // 有有效路径则当前节点计入长度，否则返回0
        return maxLength == 0 ? 0 : maxLength + 1;
    }

    public static boolean isValid(int x, int y, int n, String[][] park) {
        if (x >= 0 && x < n && y >= 0 && y < n) {
            return !park[y][x].equals("$");
        }
        return false;
    }
}

关键修复点 #

• 替换访问标记结构：用boolean[][] visited代替LinkedList<Integer[]>，直接通过坐标索引判断访问状态，既高效又避免对象引用比较的坑。
• 修正递归逻辑：
  1. 先判断当前节点是否为终点，提前终止无效遍历；
  2. 遍历方向时，取所有分支的最大路径长度，而非累加；
  3. 增加回溯操作：递归返回后将当前节点的访问标记设为false，确保其他分支可以正常访问该节点。
• 简化方向遍历：用二维数组存储四个方向的偏移量，代码更简洁易维护。
• 无路径处理：若最终返回0，说明s到t没有有效路径，输出-1提示。

测试用例说明 #

你提供的测试用例中，s(0,0)到t(2,0)的路径被$(1,0)阻挡，实际无有效路径，修复后的代码会输出-1。若调整测试用例为可通行路径（比如把$换成#），代码会正确返回最长路径的节点数。

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