如何獲取常見數據包圍的矩陣位置？

Question

我在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」是不規則圖形的周長，並且在其周圍的區域（在這種情況下：a [2] [3]，a [3] [1]，a [3] [ 2]，a [3] [3]，a [3] [4]，a [4] [2]和a [4] [4]）。

我怎樣才能自動獲得這些職位？

Answer 1

一個做你想要什麼樣的方式是使用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 + "]"); 
      } 
     } 
    } 
} 

這種特殊的實現是好的，因爲它會爲任意大小和形狀的數組。我添加了一點來檢查一個點是否也在一個不規則數組的邊緣（比較這些行的長度）。

輸出正是你所期望的：

[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 

注意，它可以容易地擴展到非正方形矩陣。

多米尼克Ubersfeld