解决网格路径查找算法中无限循环问题

import java.awt.Color; // 假设 Color 类存在于此
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Queue; // 虽然原代码用Queue，但这里我们用Deque作为栈或队列

// 假设 Point 和 Rectangle 类定义如下，并包含 isValid 方法
// class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } boolean isValid(int gridWidth, int gridHeight) { return x >= 0 && x < gridWidth && y >= 0 && y < gridHeight; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Point point = (Point) o; return x == point.x && y == point.y; } @Override public int hashCode() { return Objects.hash(x, y); } @Override public String toString() { return "(" + x + ", " + y + ")"; } }
// class Rectangle { Color fill; public Color getFill() { return fill; } }

public class PathFinder {

    // 假设 Point 类有一个 x() 和 y() 方法，对应 x 和 y 坐标
    // 为了与原始代码兼容，我们假设 Point 是一个记录（record）或有一个公共的 x, y 字段
    // 如果 Point 是一个 record class Point(int x, int y) {}
    // 如果是普通类，需要 Point.x 和 Point.y
    // 这里为了演示，我们假设 Point 有 x() 和 y() 方法
    // 实际项目中请根据 Point 类的具体实现进行调整
    private static class Point {
        int x, y;
        public Point(int x, int y) { this.x = x; this.y = y; }
        public int x() { return x; }
        public int y() { return y; }
        public boolean isValid(int gridWidth, int gridHeight) {
            return x >= 0 && x < gridWidth && y >= 0 && y < gridHeight;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }
        @Override
        public int hashCode() {
            return java.util.Objects.hash(x, y);
        }
        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }

    // 假设 Rectangle 类有一个 getFill() 方法返回 Color
    private static class Rectangle {
        Color fill;
        public Rectangle(Color fill) { this.fill = fill; }
        public Color getFill() { return fill; }
    }


    public Deque<Point> findPath(Rectangle[][] matrix, Point destPoint) {
        // 定义移动方向：右、下、左、上
        var dir = new ArrayList<Point>();
        dir.add(new Point(1, 0)); // right
        dir.add(new Point(0, 1)); // down
        dir.add(new Point(-1, 0)); // left
        dir.add(new Point(0, -1)); // up

        Point start = new Point(0, 0); // 起始点固定为 (0,0)

        // availablePaths 存储所有待探索的完整路径
        // 每个元素本身是一个 Deque<Point>，代表一条从起点到当前点的完整路径
        Deque<Deque<Point>> availablePaths = new ArrayDeque<>();

        // 初始化：将起始点作为第一条路径加入待探索集合
        Deque<Point> initialPath = new ArrayDeque<>();
        initialPath.add(start);
        availablePaths.add(initialPath);

        // 当还有待探索的路径时，循环继续
        while (!availablePaths.isEmpty()) {
            // 从 availablePaths 中取出一个路径进行探索
            // removeLast() 使得它表现得像一个栈，实现深度优先搜索 (DFS)
            // 如果使用 removeFirst()，则实现广度优先搜索 (BFS)
            Deque<Point> currentPath = availablePaths.removeLast();
            Point currentPoint = currentPath.getLast(); // 获取当前路径的最后一个点

            // 检查是否已到达目标点
            if (currentPoint.equals(destPoint)) {
                return currentPath; // 找到路径，返回
            }

            // 探索当前点的所有可能邻居
            for (int dc = 0; dc < dir.size(); dc++) {
                Point nextMove = new Point(currentPoint.x() + dir.get(dc).x(), currentPoint.y() + dir.get(dc).y());

                // 检查移动是否在网格范围内
                if (!nextMove.isValid(matrix[0].length, matrix.length)) {
                    continue;
                }

                // 检查新点是否已经在当前路径中，避免形成循环
                if (currentPath.contains(nextMove)) {
                    continue;
                }

                // 检查新点是否是墙壁 (MAGENTA)
                if (matrix[nextMove.y()][nextMove.x()].getFill() != Color.MAGENTA) {
                    // 如果是有效且未访问过的点，则创建一条新路径
                    // 新路径是当前路径的副本，并添加新点
                    Deque<Point> newPath = new ArrayDeque<>(currentPath);
                    newPath.add(nextMove);
                    availablePaths.add(newPath); // 将新路径加入待探索集合
                }
            }
        }

        // 如果所有路径都探索完毕仍未找到目标，则返回 null
        return null;
    }
}