在二維數組中找到連接的單元

我正在用Java實現一個棋盤遊戲，需要開發一個算法來查找2d數組中單個單元格中「連接」單元的數量。

編輯：通過連接，我的意思是具有與我開始的單元格相同的值。如果方法調用值爲x的單元格，我需要找到所有與它共享邊緣的元素（而不是對角線）。

IE，如果我有一和零的這種二維數組，我想找到連接細胞的數量最多時我選擇的單細胞：

[1][1][1][0] 
[1][0][1][1] 
[1][0][0][1] 
[1][0][0][1]

運行的算法[0] [0 ]會返回10，因爲有6個1s連接沿着正確的路徑，3個沿着左邊的路徑連接。

有沒有一種已知的方法來解決這個問題？如果不是，你會如何解決它？我在絞盡腦汁，似乎無法找到一條脫離蝙蝠的路。任何建議表示讚賞。

來源

2014-02-12 Ladybro

可以請你通過你的意思的「連接」細胞 – Mozzie

解釋什麼更多你的意思是最長的非循環路徑從當前單元格開始的長度，並只訪問具有相同價值的單元格？如果是這樣，它是否包括對角線運動？如果沒有，請澄清一下，因爲你對「連接」的定義很難理解。 –

對不起，我感到困惑。通過連接，我的意思是單元1）具有與原始值相同的值（在我的例子中，'1'），並且2）與它所連接的單元共享邊（對角線不構成連接）。 – Ladybro

您可能需要查看一些路徑查找算法。

最常見的，速度最快的是Dijkstra's Algorithm

的consept是很容易理解和執行。而不是尋找一條路徑，你可以找到你正在搜索的區域周圍的1或0。

看看Dijkstra算法在二維數組上的路徑發現。 Path Finding

通過查看您的環繞「節點」（1或0's），您可以找到「連接」部分。

來源

2014-02-12 01:46:23 Mozzie

檢查深度優先搜索。遞歸算法的想法如下：

創建空單元堆棧。
添加到堆棧的起始位置（例如0,0）。
拉堆棧你的電池（這意味着 - 從堆棧中刪除它，並準備去探索吧）和探索什麼相鄰細胞中，這種細胞有，添加符合你條件的所有相鄰單元（== 1並分享邊緣）到同一個堆棧。馬克拉如所見。
重複＃3，直到您在表格中看不到細胞，或者您面對的是沒有任何細胞符合您的條件或堆棧變爲空的相鄰細胞組。

你應該以某種方式記住你傳遞的方式，選擇最長的一個（包含多個1S）

這是非常簡單的和短期的算法。祝你好運！

來源

2014-02-12 02:08:11

解決它，這是我做的：

// Java the board game: find connected spaces 

public class findConnectedCells 
{ 
    public static int findNumberConnected(int a, int b, int[][] z) 
    { 
     boolean canUp = (a - 1 >= 0); 
     boolean canDown = (a + 1 < z.length); 
     boolean canRight = (b + 1 < z[0].length); 
     boolean canLeft = (b - 1 >= 0); 

     int value = z[a][b]; 

     int up = 0; 
     int down = 0; 
     int right = 0; 
     int left = 0; 

     z[a][b] = 2; 

     if (canUp && z[a-1][b] == value) 
     { 
      up = findNumberConnected(a-1,b,z); 
     } 
     if (canDown && z[a+1][b] == value) 
     { 
      down = findNumberConnected(a+1,b,z); 
     } 
     if (canLeft && z[a][b-1] == value) 
     { 
      left = findNumberConnected(a,b-1,z); 
     } 
     if (canRight && z[a][b+1] == value) 
     { 
      right = findNumberConnected(a,b+1,z); 
     } 

     return up + left + right + down + 1; 
    } 


    public static void main(String[] args) { 
     System.out.println("Finding connections"); 

     int[][] z = new int[][]{ 

         { 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1 }, 
         { 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1 }, 
         { 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1 }, 
         { 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1 }, 
         { 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1 }, 
        }; 
     int x = 0; 
     int y = 0; 

     System.out.println("Number of connected cells from "+x+","+y+" is: "+findNumberConnected(x,y,z)); 
    } 
}

來源

2014-02-12 02:25:18 Ladybro

我有一種奇怪的感覺，你還沒有測試過這個算法。我預計在不久的將來會出現堆棧溢出異常。 –

我最初得到了一個堆棧溢出異常，但將索引標記爲2以表示該索引之前已經訪問過，從而修復了該錯誤。隨意自己測試一下代碼。 – Ladybro

哦，我的錯。我錯過了那部分。我認爲第三個和第四個if塊中的'up ='只是印刷錯誤（可能應該是「左」和「右」）？我仍在考慮是否會陷入所有可能的情況。 –

深度優先搜索的關鍵算法和更好的辦法來解決，因爲如果陣列中的每個維度大的數字，那麼你將得到計算器例外 。首先，將細胞連接到過去，就像下面的東西一樣;左上，上，右上和左。這將涵蓋所有可能的聯繫。

_ _ _ 
_ x

然後，一旦您有效地連接單元格，只需在所有矩陣中進行深度優先遍歷。當你在這個區域時，不斷增加區域數量，就像你先完成深度第一次遍歷一樣，然後直到你再次找到一個未訪問的節點並且執行相同的操作。如果新區域數量較大，則將其替換爲迄今爲止最大的區域數量。

下面是實現

import java.util.LinkedList; 
import java.util.List; 
import java.util.Scanner; 
import java.util.Stack; 
import java.util.stream.Stream; 

public class SolutionNoRecursion { 

    public static void main(String[] args) { 

     Scanner in = new Scanner(System.in);   
     int row = Integer.valueOf(in.nextLine()); 
     Node[][] matrix = new Node[row][Integer.valueOf(in.nextLine())]; 

     int count = 0; 

     LinkedList<Node> nodes = new LinkedList<>(); 

     while(row-->0){    
      int[] numbers = Stream.of(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); 

      for (int column = 0; column < numbers.length; column++) { 
       if(numbers[column] == 1){      
        Node node = new Node(); 
        nodes.add(node); 
        matrix[count][column] = node; 
        if(count > 0 && count <= matrix.length){ 
         Node upperNode = matrix[count-1][column]; 
         connectNodesToEachOther(node, upperNode); 
         if(column < numbers.length-1){ 
          Node upperRightNode = matrix[count-1][column+1]; 
          connectNodesToEachOther(node, upperRightNode); 
         } 
        } 

        if(column > 0){ 
         Node leftNode = matrix[count][column-1]; 
         connectNodesToEachOther(node, leftNode); 
        } 

        if(column>0 && count>0){ 
         Node upperLeftNode = matrix[count-1][column-1]; 
         connectNodesToEachOther(node, upperLeftNode); 
        }           
       }     
      } 
      count++; 
     } 
     in.close(); 


     int maxSoFar = 0; 
     for (Node node : nodes) { 
      if(node.visited){ 
       continue; 
      } 
      node.visited = true; 
      int regionCount = 1; 
      Stack<Node> stack = new Stack<>(); 
      stack.push(node); 
      while(!stack.empty()){ 
       Node connection = stack.pop(); 
       if(!connection.visited){ 
        connection.visited = true; 
        regionCount++; 
       } 
       for(Node nodeCon : connection.connections){ 
        if(!nodeCon.visited){ 
         stack.push(nodeCon);       
        } 
       } 
      } 
      maxSoFar = regionCount > maxSoFar ? regionCount : maxSoFar; 
     } 

     System.out.println(maxSoFar); 
    } 

    protected static void connectNodesToEachOther(Node node, Node upperNode) { 
     if(upperNode != null){ 
      node.connections.add(upperNode); 
      upperNode.connections.add(node); 
     } 
    } 

} 

class Node{ 
    boolean visited = false; 
    List<Node> connections = new LinkedList<>(); 
}

來源

2016-08-21 21:13:02

在二維數組中找到連接的單元

回答

相關問題