一尘不染

Java-查找连接数最多的算法

algorithm

我有问题,但似乎找不到其他尝试执行类似任务的人。我在整数数组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

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


阅读 252

收藏
2020-07-28

共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”。

2020-07-28