在二维数组中找到连接的单元

我正在用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

在二维数组中找到连接的单元

回答

相关问题