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

import java.awt.Color;
import java.awt.Point; // 假设 Point 类有 x() 和 y() 方法，以及 isValid 方法
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Queue;

// 假设 Rectangle 和 Point 类定义如下，以支持示例
// 实际项目中，Rectangle 可能是自定义的网格单元格对象
class Rectangle {
    private Color fill;
    public Rectangle(Color fill) { this.fill = fill; }
    public Color getFill() { return fill; }
    public void setFill(Color fill) { this.fill = fill; }
}

// 假设 Point 类有 isValid 方法
// 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) { ... }
//     @Override
//     public int hashCode() { ... }
// }


public class PathfindingSolver {

    /**
     * 在网格中查找从 (0,0) 到目标点的路径。
     *
     * @param matrix 网格矩阵，每个单元格可以是障碍物（MAGENTA）或可通行区域。
     * @param destPoint 目标点。
     * @return 如果找到路径，返回一个包含从起点到目标点所有点的队列（不包含起点）；否则返回 null。
     */
    public Queue<Point> findPath(Rectangle[][] matrix, Point destPoint) {
        // 定义移动方向：右、下、左、上
        var dir = new ArrayList<Point>();
        dir.add(new Point(1, 0));  // 右
        dir.add(new Point(0, 1));  // 下
        dir.add(new Point(-1, 0)); // 左
        dir.add(new Point(0, -1)); // 上

        Point start = new Point(0, 0);

        // 使用 Deque 来存储所有待探索的路径。
        // 每个元素都是一个 Deque<Point>，代表一条从起点到当前点的完整路径。
        // ArrayDeque 可以作为栈（removeLast）或队列（removeFirst）使用。
        // 此处使用 removeLast() 模拟深度优先搜索 (DFS) 的行为。
        Deque<Deque<Point>> availablePaths = new ArrayDeque<>();

        // 初始化：创建第一条路径，只包含起点，并将其加入待探索集合。
        Deque<Point> initialPath = new ArrayDeque<>();
        initialPath.add(start);
        availablePaths.add(initialPath);

        // 主循环：只要还有待探索的路径
        while (!availablePaths.isEmpty()) {
            // 从集合中取出一个路径进行探索。
            // removeLast() 实现深度优先搜索。若要实现广度优先搜索，请使用 removeFirst()。
            Deque<Point> currentPath = availablePaths.removeLast();

            // 获取当前路径的最后一个点，即当前探索的节点
            Point currentPoint = currentPath.getLast();

            // 检查当前点是否为目标点
            if (currentPoint.equals(destPoint)) {
                // 如果是目标点，则找到路径。
                // 根据需求，如果返回的路径不包含起点，则可以 currentPath.poll()。
                // 示例中直接返回完整路径。
                return currentPath;
            }

            // 探索当前点的所有相邻方向
            for (int i = 0; i < dir.size(); i++) {
                Point moveDirection = dir.get(i);
                Point nextMove = new Point(currentPoint.x() + moveDirection.x(), currentPoint.y() + moveDirection.y());

                // 1. 检查新点是否在网格边界内
                if (!nextMove.isValid(matrix[0].length, matrix.length)) {
                    continue; // 超出边界，跳过
                }

                // 2. 检查新点是否已在当前路径中 (防止回溯和无限循环)
                if (currentPath.contains(nextMove)) {
                    continue; // 避免路径在自身上形成循环，跳过
                }

                // 3. 检查新点是否为障碍物 (MAGENTA)
                if (matrix[nextMove.y()][nextMove.x()].getFill() != Color.MAGENTA) {
                    // 如果新点有效且可通行，则创建一条新的路径
                    // 新路径是当前路径的副本，并添加了新点
                    Deque<Point> newPath = new ArrayDeque<>(currentPath);
                    newPath.add(nextMove);

                    // 将新路径添加到待探索的路径集合中
                    availablePaths.add(newPath);
                }
            }
        }

        // 如果循环结束仍未找到目标点，则表示无路径可达
        return null;
    }
}