Java – 查找大多数连接数字的算法

我有一个问题，但似乎找不到其他人试图做类似的任务。 我在int数组grid [] []中有一个数字网格

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 6 2 3 4 9 7
 3 3 3 4 7 8 9
 3 3 1 2 3 1 4
 9 7 4 1 2 3 4 

我需要一个简单的算法，通过上，下，左，右连接找到连接数最多的地方。 所以在上面的例子中，它会在索引[2] [0]处找到3。

我知道问题可以通过简单地在循环之后执行if语句和循环来解决，但这将是非常重复但是想知道是否有更简单的方法来执行此操作？

任何帮助表示赞赏，这是我正在创建的游戏。 谢谢 ：）

编辑：帮助解决这个问题。

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 6 2 3 4 9 7
 3 3 3 4 7 8 9
 3 3 1 2 3 1 4
 9 7 4 1 2 3 4 

该方法将返回0,2作为答案，因为它会找到它

  3
 3 3 3
 3 3 

拥有最相邻的数字

另一个例子，

  2 5 1 0 8 0 8
 2 1 0 9 7 2 4
 3 3 3 3 4 6 7
 1 0 3 4 7 4 9
 3 3 3 2 3 1 6
 9 7 4 1 8 4 6 

完整的发现将是

  3 3 3 3
     3
 3 3 3 

感谢到目前为止的所有答案，深度优先搜索看起来很有趣，但到目前为止只能找到有关树样式搜索的信息。

Answer 1

也许像这样的东西可以用于小调整。 我自己没有运行它，但概念应该是清楚的。 也可以进行优化，因为可以多次评估相同的空间。

public class FindConsecutiveNumbersInGrid { public static int[][] grid = new int[][]{ {2, 5, 1, 0, 8, 0, 8}, {2, 1, 0, 9, 7, 2, 4}, {3, 3, 3, 3, 4, 6, 7}, {1, 0, 3, 4, 7, 4, 9}, {3, 3, 3, 2, 3, 1, 6}, {9, 7, 4, 1, 8, 4, 6} }; public static void main(String[] args) { int maxFound = 0; int[] maxFoundPos = new int[2]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { boolean[][] foundGrid = new boolean[grid.length][grid[0].length]; findConsecutive(i, j, foundGrid); int found = getFound(foundGrid); if (found > maxFound) { maxFound = found; maxFoundPos[0] = i; maxFoundPos[1] = j; } } } System.out.println(maxFoundPos[0] + " " + maxFoundPos[1]); } public static void findConsecutive(int i, int j, boolean[][] foundGrid) { foundGrid[i][j] = true; if (i < grid.length - 1 && grid[i][j] == grid[i+1][j] && !foundGrid[i+1][j]) { findConsecutive(i+1, j, foundGrid); } if (i > 0 && grid[i][j] == grid[i-1][j] && !foundGrid[i-1][j]) { findConsecutive(i-1, j, foundGrid); } if (j < grid[i].length - 1 && grid[i][j] == grid[i][j+1] && !foundGrid[i][j+1]) { findConsecutive(i, j+1, foundGrid); } if (j > 0 && grid[i][j] == grid[i][j-1] && !foundGrid[i][j-1]) { findConsecutive(i, j-1, foundGrid); } } public static int getFound(boolean[][] foundGrid) { int found = 0; for (boolean[] foundRow : foundGrid) { for (boolean foundSpace : foundRow) { if (foundSpace) found++; } } return found; } 

}

这打印正确“2 0”。

Answer 2

实际上，您希望找到所有连接的组件 。 BFS和DFS是关于此的着名算法。对于这个问题，你可以使用DFS。所以你假设每个数字你有一个顶点。这个顶点只通过上，下，左，右连接它们的数字是相等的。重复DFS直到所有顶点都将标记。现在找到一个在该图中具有最大数量的组件。

Answer 3

如果您只想要最大的可填充洪泛区域，那么您可以使用标准的填充填充算法 ，计算填充的节点数量，同时填充一个值，表明不应再次访问它们。 对于nxn数组，这将是O(n 2 ) ，这应该是最佳的。

如果你想要最长的序列，而不是最大的区域，那么你必须在每个洪水填充区域内搜索最长的哈密尔顿路径。 不幸的是，根据Alon Itai，Christos H. Papadimitriou和Jayme Luiz Szwarcfiter的网格图（1982）中的Hamilton Paths ，你运气不好。 我找不到非付费墙版本，但摘要似乎很清楚。 （当然，问题是NP完全的事实并不意味着它是无法解决的。也许你的N足够小以使它变得实用。）

Answer 4

我需要一个简单的算法来找到通过向下和向右连接最连续数字的位置。

一个简单的算法是遍历行和列，寻找向下和向右的最长序列。

由于您只想要第一次出现，因此您不必向左或向上看。

当你得到小于找到的最长字符串的索引时，你可以打破循环。 换句话说，一旦找到3个字符的字符串，就不必遍历最后两列和最后两行。

但是，循环整个矩阵几乎一样快，也更容易。

在你的例子中，你会发现两个3个三分的字符串，一个在（2,0），一个在（3,0）。 您只需将第一个答案作为最终答案即可。

Answer 5

您可以将其表述为动态编程问题

计算所有i，j的升序路径[i] [j] = 1的相邻路径的数量

 for i=0;i 

所有i，j的答案都是max(path[i][j]) 。

或者递归，如果你愿意的话

  for i,j0 return path[i][j] ret = 1; for dirx, diry in [(1,0),(0,1) ... etc ... ] if arr[i+dirx][j+diry] = arr[i][j] + 1 ret = max(ret, go(i+dirx,j+diry)) return ret 

Answer 6

首先找到一个未访问的单元格，然后开始递归。 免责声明：这不是java，它是没有大多数声明和标题的伪C。 无论如何，C更容易转换为java …如果需要，可以使用全局或类成员进行计数。

为了方便起见，请使用警卫围绕N * Narrays。

  // with -1 -1 -1 -1 // -1 xx -1 // -1 -1 -1 -1 for (i=N+2;i<(N+2)*(N+1);i++) { // exact starting and ending locations are disclosed if (k=array[i]!=-1) { j=1; flood_fill(array,i,k,&j); if (j>max) { max=j; max_number=k; } } } #define UP -(N+2) #define DOWN (N+2) #define LEFT -1 #define RIGHT 1 int flood_fill(int *array, int position, int value_to_compare, int *count) { // for each direction UP,DOWN,RIGHT,LEFT static const int directions[4]={UP,DOWN,RIGHT,LEFT]; int t; for (t=0;t<4;t++) if (array[position + directions[t]]==value_to_compare) { array[position + directions[t]] = -1; *count+=1; flood_fill(array, position+directions[t], value_to_compare, count); } }