如何确定矩阵中相邻元素的数量？

Question

我有一个对象数组的数组，枚举值为1或0。

可能长这样：

0 0 1 0
0 1 1 0
0 0 0 1

我想要显示包含数字 1 的组的所有成员，并显示整个组中成员的总数：

0 0 3 0
0 3 3 0
0 0 0 1

有没有已知的方法可以找出这个问题的答案？我的意思是，虽然我想要改变低于5的数字，但我可能需要为每种情况编写条件，这样会很冗长。

- Wlad

---

为什么第一行是 0 0 3 0？它应该不是 0 0 2 0，因为只有两个相邻的数字是 1。难道第二行不应该是 0 2 3 0，第三行是 0 0 0 1 吗？ - Christian Tapia

你能详细解释一下你的输出吗？你是如何计算出行是0,0,3,0而不是1,3,2,2的？你所说的“邻居”是什么意思？对角线上的元素也算邻居吗？你正在检查的元素也是它自己的邻居吗？ - Pshemo

如果不计算对角线，那么第一行的1有两个邻居和它本身，这是怎么回事呢？ - t0mppa

你希望一个团体中的所有成员都显示整个团体的成员数量？ - t0mppa

这个算法并不难，但是非常严肃和有趣。你需要找到所有的邻居，并记住它们，然后增加它们所有的值。 - Ashot Karakhanyan

Answer 1

这个问题可以通过并查集算法来解决。将您的矩阵解释为具有双向垂直和水平连接的非零节点的图形。然后，问题是在跟踪分区大小的同时找到图形的连接分区。以下是一个独立的解决方案：

public class So21503628 {
    private List<List<Integer>> matrix;
    private int h, w;
    private Map<Integer, Node> nodes = new HashMap<>();
    So21503628() {
        matrix = new ArrayList<>();
        matrix.add(Arrays.asList(0,0,1,0));
        matrix.add(Arrays.asList(0,1,1,0));
        matrix.add(Arrays.asList(0,0,0,1));
        h = matrix.size(); w = matrix.get(0).size();
    }
    void run() {
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                Node xy = nodeAt(x, y);
                if (xy == null) continue;
                Node x1y = nodeAt(x+1, y);
                if (x1y != null) union(xy, x1y);
                Node xy1 = nodeAt(x, y+1);
                if (xy1 != null) union(xy, xy1);
            }
        }
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                Node n = nodeAt(x, y);
                if (n == null) continue;
                matrix.get(y).set(x, find(n).count);
            }
        }
        System.out.println(matrix);
    }
    Node nodeAt(int x, int y) {
        if (x >= w || y >= h || matrix.get(y).get(x) == 0) return null;
        int xy = y * w + x;
        Node node = nodes.get(xy); 
        if (node == null) { node = new Node(); nodes.put(xy, node); }
        return node;
    }
    void union(Node n1, Node n2) { // unite areas if separate
        Node r1 = find(n1), r2 = find(n2);
        if (r1 != r2) { r2.parent = r1; r1.count += r2.count; }
    }
    Node find(Node n) { // find representative + compress path
        Node r = n; while (r.parent != null) r = r.parent;
        if (r != n) while (n.parent != r) { Node h = n.parent; n.parent = r; n = h; }
        return r;
    }
    static class Node { Node parent; int count = 1; }
    public static void main(String[] args) { new So21503628().run(); }
}

并查集的效率很高（接近O(n)）。 有关并查集的详细信息，请参见维基百科上的不相交集数据结构。

- halfbit

---

对于[[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 1]]，输出应该是[[0, 0, 1, 0], [2, 2, 0, 1], [0, 0, 1, 1]]；但这是错误的。我还没有学习代码，也许只是一些小错误。 - Wlad

谢谢！我修复了：在第一次遍历中使用 y<h 和 x<w 而不是 y<h-1 和 x<w-1，并在 nodeAt() 中添加对 x 和 y 的检查。 -1 的作用是优化，但会导致不尊重右端的垂直链接和底部的水平链接。 - halfbit

你的回答很好，但我并不完全理解。我正在为学校做项目，必须了解我的代码。感谢你抽出时间来帮助我。谢谢。 - Wlad

Answer 2

提醒我有点像扫雷游戏。在这里可以轻松使用递归...

public class MatrixNeighborCount
{
    public static void main(String[] args)
    {
        int array[][] = new int[][]{
            { 0, 0, 1, 0 },
            { 0, 1, 1, 0 },
            { 0, 0, 0, 1 },
        };
        int result[][] = count(array);
        print(result);
    }

    private static void print(int array[][])
    {
        for (int r=0; r<array.length; r++)
        {
            for (int c=0; c<array[r].length; c++)
            {
                System.out.printf("%3d", array[r][c]);
            }
            System.out.println("");
        }
    }

    private static int[][] copy(int array[][])
    {
        int result[][] = new int[array.length][];
        for (int i=0; i<array.length; i++)
        {
            result[i] = array[i].clone();
        }
        return result;
    }

    private static int[][] count(int inputArray[][])
    {
        int result[][] = new int[inputArray.length][];
        for (int i=0; i<inputArray.length; i++)
        {
            result[i] = new int[inputArray[i].length];
        }

        int array[][] = copy(inputArray);
        for (int r=0; r<array.length; r++)
        {
            for (int c=0; c<array[r].length; c++)
            {
                if (array[r][c] == 1)
                {
                    int count = count(array, r, c);
                    distribute(inputArray, result, r, c, count);
                }
            }
        }
        return result;
    }

    private static int count(int array[][], int r, int c)
    {
        if (!valid(array, r, c)) return 0;
        if (array[r][c] == 0) return 0;

        array[r][c] = 0;
        return 1 + 
            count(array, r-1, c) +
            count(array, r+1, c) +
            count(array, r, c-1) +
            count(array, r, c+1);
    }

    private static void distribute(
        int inputArray[][], int result[][], int r, int c, int value)
    {
        if (!valid(inputArray, r, c)) return;
        if (inputArray[r][c] == 0) return;
        if (result[r][c] != 0) return;
        result[r][c] = value;
        distribute(inputArray, result, r-1, c, value);
        distribute(inputArray, result, r+1, c, value);
        distribute(inputArray, result, r, c-1, value);
        distribute(inputArray, result, r, c+1, value);
    }

    private static boolean valid(int array[][], int r, int c)
    {
        if (r < 0) return false;
        if (r >= array.length) return false;
        if (c < 0) return false;
        if (c >= array[r].length) return false;
        return true;
    }
}

但是:

1. 对于“大型”数组，这将导致StackOverflowError。
2. 使用一些集合的解决方案可能更加优雅。

如果您描述了您正在处理的实际数据结构以及该程序的最终目的，那么这可能会有所帮助....

- Marco13

---

数据结构 - ArrayList<ArrayList>。 它将是用于过程生成地图的框架。地图可能很大，高达500x500或更多... - Wlad

顺便说一句，谢谢你的代码。现在已经是晚上了，但我明天会检查并测试它。再次感谢你。 - Wlad