java - 使用 floodfill 计算矩阵中的相邻零点

Question

我正在尝试计算每组零的邻接零的数量。我使用了 floodfill 的修改版本，它返回它填充的元素数。然后我将对 floodfill 的调用放在一个循环中。我不明白这有什么问题。

正确的输出: 2 4

当前输出: 2 2 2

public class Test {
    public static void main(String[] args) {
        String[] in = getInput();
        char[][] map = getMap(Arrays.copyOfRange(in, 0, in.length));
        House h = new House(map);
        System.out.println(h);

    }

    private static String[] getInput() {
        String[] ret = {
                "11111",
                "10011",
                "11101",
                "10001",
                "11111"
            };
        return  ret;
    }

    private static char[][] getMap(String[] copyOfRange) {
        List<char[]> ret = new ArrayList<>();
        for (String x : copyOfRange) 
            ret.add(x.toCharArray());
        return  ret.toArray(new char[ret.size()][]);
    }

}

class House {
    private char[][] map;
    List<Integer> listOfAreas;
    House(char[][] map) {
        this.map = map;
        listOfAreas = getAreas();
    }


    private List<Integer> getAreas() {
        List<Integer> ret = new ArrayList<>();
        char[][] cMap = map.clone();
        for (int i = 0; i < cMap.length; i++) {
            for (int j = 0; j < cMap[i].length; j++) {
                if (cMap[i][j] == '0')
                    ret.add(countFlood(new Point(i,j),cMap));
            }
        }
        return ret;
    }

    private int countFlood(Point start, char[][] cMap) {
        int count = 0;
        Stack<Point> stack = new Stack<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            Point p = stack.pop();
            if (cMap[p.getX()][p.getY()] == '0') {
                ++count;
                cMap[p.getX()][p.getY()] = '1';
                for (Point x : getAdj(p,cMap))
                    stack.push(x);

            }
        }
        return count;
    }

    private Point[] getAdj(Point p, char[][] cMap) {
        List<Point> ret = new ArrayList<Point>();
        if (p.getX() == 0)
            ret.add(new Point(p.getX() - 1, p.getY()));
        if (p.getX() != cMap.length - 1)
            ret.add(new Point(p.getX() + 1, p.getY()));
        if (p.getY() == 0)
            ret.add(new Point(p.getX(), p.getY() - 1));
        if (p.getY() != cMap[p.getX()].length - 1)
            ret.add(new Point(p.getX(), p.getY() + 1));

        return ret.toArray(new Point[ret.size()]);
    }


    public String toString() {
        StringBuilder ret = new StringBuilder();
        for (int x : listOfAreas)
            ret.append(x + " ");

        return ret.toString();
    }

}

class Point {
    private int x;
    private int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

Answer 1

问题出在您的 getAdj 代码中:您添加的点只有在相应坐标为零时才向下和向左移动；你应该只在它不为零时添加:

private Point[] getAdj(Point p, char[][] cMap) {
    List<Point> ret = new ArrayList<Point>();
    if (p.getX() != 0) // <<== Use != instead of ==
        ret.add(new Point(p.getX() - 1, p.getY()));
    if (p.getX() != cMap.length - 1)
        ret.add(new Point(p.getX() + 1, p.getY()));
    if (p.getY() != 0) // <<== Use != instead of ==
        ret.add(new Point(p.getX(), p.getY() - 1));
    if (p.getY() != cMap[p.getX()].length - 1)
        ret.add(new Point(p.getX(), p.getY() + 1));

    return ret.toArray(new Point[ret.size()]);
}