如何获得由公共数据包围的矩阵位置？

我在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]和[4] [4]）。

我怎样才能自动获得这些职位？

Answer 1

做你想做的事情的一种方法是使用洪水填充 ，没有填充对角线。 这对您自己没有帮助，但您可以使用一些非零值填充连接到数组边缘的所有区域。 数组中剩余的零将是您渴望的元素。

这是一个简单的洪水填充实现：

 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 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 + "]"); } } } } 

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

输出正是您所期望的：

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

Answer 2

这是一个简单的算法，它使用辅助函数来计算每个元素的前驱和后继的索引。

 public class Test { public static final int N = 6; public static int isucc(int i, int j) { return (i * N + j + 1) / N; } public static int jsucc(int i, int j) { return (i * N + j + 1) % N; } public static int ipred(int i, int j) { return (i * N + j - 1) / N; } public static int jpred(int i, int j) { return (i * N + j - 1) % N; } public static void main(String[] args) { 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} }; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i * N + j > 0 && i * N + j < N * N - 1 && a[ipred(i,j)][jpred(i,j)] == 1 && a[isucc(i,j)][jsucc(i,j)] == 1) { System.out.println(i + "," + j); } } } } } 

它打印：

 2,3 2,5 4,0 4,2 4,4 5,3 

请注意，它可以很容易地扩展到非方形矩阵。

多米尼克·尤伯斯费尔德