java - BFS 问题返回值始终为空

Question

我正在研究这个算法，但无法弄清楚为什么我总是得到一个空返回。代码添加到两个数组 fx 和 fy，它收集 x 和 y 位置，这些位置将以最短路径完成迷宫。问题是没有任何东西被添加到数组中。有什么建议么？

 public class Maze {

        public List<Integer> fx;
        public List<Integer> fy;
        public int listSize;
        public Point p;
        public int[][] cells;

        public Maze(int x, int y, int[][] cells) {

            p = getPathBFS(x, y, cells);
            this.cells = cells;

            fx = new ArrayList<>();
            fy = new ArrayList<>();
            addPoint();     
        }

        private static class Point {
            int x;
            int y;
            Point parent;

            public Point(int x, int y, Point parent) {
                this.x = x;
                this.y = y;
                this.parent = parent;      
            }

            public Point getParent() {
                return this.parent;
            }      
        }

        public static Queue<Point> q = new LinkedList<>();

        public Point getPathBFS(int x, int y, int[][] cells) {

            q.add(new Point(x, y, null));

            while (!q.isEmpty()) {

                Point p = q.remove();

                if (cells[p.x][p.y] == 9) {
                    return p;
                }

                if (isFree(p.x + 1, p.y, cells.length, cells)) {

                    cells[p.x][p.y] = 2;
                    Point nextP = new Point(p.x + 1, p.y, p);
                    q.add(nextP);
                }

                if (isFree(p.x - 1, p.y, cells.length, cells)) {
                    cells[p.x][p.y] = 2;
                    Point nextP = new Point(p.x - 1, p.y, p);
                    q.add(nextP);
                }

                if (isFree(p.x, p.y + 1, cells.length, cells)) {
                    cells[p.x][p.y] = 2;
                    Point nextP = new Point(p.x, p.y + 1, p);
                    q.add(nextP);
                }

                if (isFree(p.x, p.y - 1, cells.length, cells)) {
                    cells[p.x][p.y] = 2;
                    Point nextP = new Point(p.x, p.y - 1, p);
                    q.add(nextP);
                }

            }

            return null;
        }

        public static boolean isFree(int x, int y, int cellLength, int[][] cells) {

            if ((x >= 0 && x < cellLength) && (y >= 0 && y < cells[x].length) && (cells[x][y] == 0 || cells[x][y] == 9)) {
                return true;
            }
            return false;
        }

        public synchronized void addPoint() {
            System.out.println(p);
            while ((p != null)) {

                System.out.println("x is " + p.x + " - y is " + p.y);

                fy.add(p.x);
                fx.add(p.y);
                p = p.getParent();
            }
        }

        int getListSize() {
            listSize = fx.size() - 1;        
            return listSize;
        }
  }

标签： javabreadth-first-search