时间戳

首页 > 解决方案 > Java中BFS的结果不一致

java - Java中BFS的结果不一致

问题描述

当第一次创建新的迷宫对象时，此代码可以正常工作。然而，当 BFS 完成并再次玩游戏（通过让用户选择再次玩）时，算法不会有效地工作。最终目标仍然得到满足，但是 x 和 y 坐标被添加到不属于最短路径的数组中。我从未见过我的第一次运行错误地完成了搜索，但是后续实例确实如此。似乎每次创建新的迷宫对象时，迷宫都会受到前一个实例的影响。有输入吗？

public class Maze {

    public static List<Integer> fx;
    public static List<Integer> fy;
    public static int listSize;
    public static Point p;

    public Maze(int x, int y) {

        p = getPathBFS(x, y);
        fx = new ArrayList<>();
        fy = new ArrayList<>();
        addPoint();

        System.out.print("next");
    }

    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 static Point getPathBFS(int x, int y) {

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

        while (!q.isEmpty()) {
            Point p = q.remove();

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

            if (isFree(p.x + 1, p.y)) {
                Level.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)) {
                Level.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)) {
                Level.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)) {
                Level.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) {
        if ((x >= 0 && x < Level.cells.length) && (y >= 0 && y < Level.cells[x].length) && (Level.cells[x][y] == 0 || Level.cells[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void addPoint() {

        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();
        }

    }

    public static int getListSize() {
        listSize = fx.size();

        return listSize;
    }
}

标签： javabreadth-first-search

解决方案

似乎每次创建新的迷宫对象时，迷宫都会受到前一个实例的影响

对，就是这样。您的所有字段都被声明为静态。静态字段在所有实例中都是通用的，而不仅仅是一个。您可以在所有（或几乎所有）实例中删除 static 关键字。

public static List<Integer> fx;
public static List<Integer> fy;
public static int listSize;
public static Point p;

看起来您的Level班级也遇到了同样的问题：

Level.cells.length

我会研究“静态”的实际含义，因为您似乎在没有真正理解它的情况下使用它。

推荐阅读