4

我有一个问题，但似乎找不到其他尝试过类似任务的人。我在 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

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

4

6 回答 6

2

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

于 2013-03-13T21:05:44.520 回答
1

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

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

于 2013-03-13T19:49:32.817 回答
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”。

于 2013-03-13T20:01:43.093 回答
0

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

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

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

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

但是，循环遍历整个矩阵几乎同样快速且容易得多。

在您的示例中，您会发现两个由 3 个三点组成的字符串，一个在 (2,0)，一个在 (3,0)。您只需将第一个答案作为最终答案。

于 2013-03-13T19:41:45.040 回答
0

您可以将其表述为动态规划问题

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

for i=0;i<n 
  for j=0;j<n
     for dirx, diry in [(1,0),(0,1) ... etc ... ]
        if arr[i+dirx][j+diry] = arr[i][j] + 1
           path[i+dirx][j+diry] += path[i][j]

答案将max(path[i][j])适用于所有 i,j。

或者递归，如果你喜欢

   for i,j<n
       go(i,j)

   def go(i,j)
        if path[i][j]>0 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
于 2013-03-13T19:43:56.687 回答
0

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

为了让事情变得更容易，用警卫包围你的 N*N 数组。

    // with -1 -1 -1 -1 
    //      -1  x  x -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);
    }
}
于 2013-03-13T19:53:21.623 回答