確定網格中分組值的數量

Question

想知道是否有人可以用一些邏輯來幫助我。

說我有一個包含的網格：

1 2 3 
1 A B A 
2 A B B 
3 A A B 

有3組在該網格中，這是由每個單元的值和所有具有相同值的相鄰小區來確定，所以假設座標方案是（COL，行）：

組1：（1,1），（1,2），（1,3），（2,3），其具有

組2的一個值： （2,1），（2,2），（3,2），（3,3），其值爲B

組3：（3,1）其值爲A

任何人都可以建議我如何確定這個編程？

我的線沿線的思考：

• 使用for循環通過網格
  • 有哪些檢查電池的頂部，右側，底部和左側的單元格的值（也有方法來迭代佔邊界單元）
    • 檢查細胞是相同的值，然後存儲它在某種程度上
    • 否則，它是一個新的組？
  • 遞歸

但我不能得到解決，如果發現有不同值的單元格做什麼。我認爲我在這裏簡化了一個簡單的解決方案。

我最好喜歡存儲與網格內所有組相關的座標數組。

Answer 1

我認爲處理這個概念上最簡單的方法是遞歸。當然，由於Java的subpar尾遞歸支持，迭代解決方案會更有效率;遞歸仍然適用於小的值。

看看此示例代碼

public static void main(String[] args) { 
    int xBound = 3; 
    int yBound = 3; 
    String[][] grid = new String[][] { 
     {"A", "B", "A"}, 
     {"A", "B", "B"}, 
     {"A", "A", "B"} 
    }; 

    for(int i = 0; i < yBound; i++) { 
     for(int j = 0; j < xBound; j++) { 
      String state = grid[i][j]; 
      List<List<Integer>> group = getGroup(state, j, i, xBound, yBound, grid); 
      if (group.size() != 0) { 
       System.out.println(state + " " + group); 
      } 
     } 
    } 
} 

static List<List<Integer>> getGroup(String state, int xIndex, int yIndex, int xBound, int yBound, String[][] grid) { 
    if (xIndex >= xBound || xIndex < 0 || yIndex >= yBound || yIndex < 0 || grid[yIndex][xIndex].equals("USED")) { 
     return new ArrayList<>(); 
    } else if (grid[yIndex][xIndex].equals(state)){ 
     grid[yIndex][xIndex] = "USED"; 

     List<List<Integer>> ourPosse = new ArrayList<List<Integer>>(); 
     ourPosse.add(Arrays.asList(yIndex, xIndex)); 
     ourPosse.addAll(getGroup(state, xIndex + 1, yIndex, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex - 1, yIndex, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex, yIndex + 1, xBound, yBound, grid)); 
     ourPosse.addAll(getGroup(state, xIndex, yIndex - 1, xBound, yBound, grid)); 

     return ourPosse; 
    } else { 
     return new ArrayList<>(); 
    } 
} 

我們通過網格步驟，欲以每個條目作爲新組的「根」。如果一個獨立的組實際上植根於該條目（即grpCt！= 0），那麼我們就打印它。

在getGroupMethod中，我們首先檢查我們是否已經離開了網格邊界，或者我們是否已經在前一個組中使用了條目。請注意，這種檢查是通過改變網格完成的，但我們可以保留備忘錄。否則，如果當前條目與我們希望分組的狀態相匹配，那麼我們將此條目添加到組中，然後向所有方向擴展，查找要添加到組的其他條目。

否則，我們知道當前條目不能成爲組的一部分。

編輯：就漸近運行時間而言，因爲我們通過在網格中設置標誌來有效地記憶，因此最多隻考慮每個條目4次，所以我們得到了O（n^2）。