Java网格路径查找算法优化：解决无限循环与实现深度优先探索

import java.awt.Color;
import java.awt.Point; // 使用 java.awt.Point
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Objects;
import java.util.Queue;

// 假设 Rectangle 类具有 getFill() 方法
// 实际项目中可能来自 GUI 库
class GridRectangle {
    private Color fill;
    public GridRectangle(Color fill) { this.fill = fill; }
    public Color getFill() { return fill; }
}

// 假设 Point 类（或其扩展）具有 isValid 方法
// java.awt.Point 默认没有 isValid，这里为演示添加
// 并且为了在集合中正确比较，需要重写 equals 和 hashCode
class GridPoint extends Point {
    public GridPoint(int x, int y) {
        super(x, y);
    }

    // 检查点是否在网格范围内
    public boolean isValid(int gridWidth, int gridHeight) {
        return x >= 0 && x < gridWidth && y >= 0 && y < gridHeight;
    }

    // 重写 equals 和 hashCode 以确保在集合中正确比较
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        GridPoint gridPoint = (GridPoint) o;
        return x == gridPoint.x && y == gridPoint.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

public class PathfindingSolver {

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

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

        // 存储所有待探索的路径。每个Deque<GridPoint>代表一条从起点到当前点的完整路径。
        // 使用 Deque 作为 Queue 的实现，因为它提供了 removeLast() 来实现 DFS
        Deque<Deque<GridPoint>> availablePaths = new ArrayDeque<>();

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

        // 当还有待探索的路径时，继续循环
        while (!availablePaths.isEmpty()) {
            // 从集合中取出一条路径进行探索。
            // removeLast() 实现深度优先搜索 (DFS)。
            // 若使用 removeFirst() 则实现广度优先搜索 (BFS)。
            Deque<GridPoint> currentPath = availablePaths.removeLast();
            GridPoint currentPoint = currentPath.getLast(); // 获取当前路径的末端点

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

            // 探索当前点的所有可能移动方向
            for (int dc = 0; dc < dir.size(); dc++) {
                GridPoint move = new GridPoint(currentPoint.x + dir.get(dc).x, currentPoint.y + dir.get(dc).y);

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

                // 2. 关键改进：检查移动点是否已经被当前路径访问过，防止循环
                if (currentPath.contains(move)) {
                    continue;
                }

                // 3