如何获得公共数据包围的矩阵位置? [英] How to get matrix positions surrounded by common data?

问题描述

我在Java中定义了一个矩阵

I have a defined matrix in Java

int[][] a={
    {0,0,0,0,0,0},
    {0,0,0,1,0,0},
    {0,1,1,0,1,0},
    {1,0,0,0,0,1},
    {0,1,0,1,0,1},
    {0,0,1,0,1,0}
};

所以我想知道矩阵的哪些位置被"1"值构成的线所包围，即值"0"的位置组，好像"1"是不规则图形的周长，以及其范围内的周长内的"0"值(在这种情况下:a [2] [3]，a [3] [1]，a [3] [2]，a [3] [3]，a [ 3] [4]，a [4] [2]和a [4] [4]).

So I want to know what positions on matrix are surrounded by the lines made of "1" values, i.e., the group of positions with value of "0", as if the "1" were the perimeter of a irregular figure, and "0" values within the perimeter its area (in this case: a[2][3], a[3][1], a[3][2], a[3][3], a[3][4], a[4][2] and a[4][4]).

我如何自动获得这些职位?

How can I get these positions automatically?

推荐答案

一种执行所需操作的方法是使用

One way to do what you want is to use flood fill, with no filling across diagonals. This will not help you by itself, but you can fill all regions that are connected to the edges of your array with some non-zero value. The remaining zeros in the array will be the elements that you crave.

这是洪水填充的简单实现:

Here is a simple implementation of flood fill:

import java.util.ArrayDeque;
import java.awt.Point;  // This is probably superfluous, an int[] with two elements would do fine here too

public class Test
{
    private static int[][] a = new int[][] {
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 1, 1 ,0, 1, 0},
        {1, 0, 0, 0, 0, 1},
        {0, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 1, 0}
    };

    /*
     * Applies flood fills all elements accessible from array[row][col] with
     * value. If the element at (row, col) is already value, this method does
     * nothing.
     */
    private static void floodFill(int[][] array, int row, int col, int value)
    {
        int oldValue = array[row][col];
        if(oldValue == value)
            return;
        ArrayDeque<Point> queue = new ArrayDeque<>();
        queue.add(new Point(col, row));
        while(queue.size() > 0) {
            // Technically, removeLast would be more efficient, especially
            // since the order does not matter, but this is just an example
            Point point = queue.pop();
            int r = point.y;
            int c = point.x;
            array[r][c] = value;

            if(r > 0 && array[r - 1].length > c && array[r - 1][c] == oldValue)
                queue.add(new Point(c, r - 1));
            if(r < array.length - 1 && array[r + 1].length > c && array[r + 1][c] == oldValue)
                queue.add(new Point(c, r + 1));
            if(c > 0 && array[r][c - 1] == oldValue)
                queue.add(new Point(c - 1, r));
            if(c < array[r].length - 1 && array[r][c + 1] == oldValue)
                queue.add(new Point(c + 1, r));
        }
    }

    /*
     * Walks around the edges of the array and floods everthing connected to
     * them with ones. This relies on floodFill exiting early for areas that
     * were already filled.
     */
    private static void fillEdges(int[][] array)
    {
        // top row
        for(int col = 0; col < array[0].length; col++)
            floodFill(array, 0, col, 1);
        // left column
        for(int row = 0; row < array.length; row++)
            floodFill(array, row, 0, 1);
        // bottom row
        for(int col = 0; col < array[array.length - 1].length; col++)
            floodFill(array, array.length - 1, col, 1);
        // all trailing row segments (allows for ragged arrays)
        for(int row = 1; row < array.length - 1; row++) {
            int lengthToFill = array[row].length - Math.min(array[row - 1].length, array[row + 1].length);
            lengthToFill = (lengthToFill < 0) ? 1 : lengthToFill + 1;
            for(int col = array[row].length - lengthToFill; col < array[row].length; col++)
                floodFill(array, row, col, 1);
        }
    }

    public static void main(String[] args)
    {
        fillEdges(a);
        for(int row = 0; row < a.length; row++) {
            for(int col = 0; col < a[row].length; col++) {
                if(a[row][col] == 0)
                    System.out.println("[" + row + "][" + col + "]");
            }
        }
    }
}

这个特殊的实现很好，因为它将适用于任意大小和形状的数组.我还添加了一点检查点是否也在参差不齐的数组的边缘(比较行的长度).

This particular implementation is nice because it will work for arrays of arbitrary size and shape. I added a bit to check if a point is on the edge of a ragged array as well (comparing the lengths of the rows).

输出正是您所期望的:

[2][3]
[3][1]
[3][2]
[3][3]
[3][4]
[4][2]
[4][4]

这篇关于如何获得公共数据包围的矩阵位置?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！