爪哇 - 算法寻找最连接数 [英] Java - Algorithm to find most connected numbers

问题描述

我有一个问题，但似乎无法找到任何其他人试图做类似的工作。我有一个数字网格在一个int数组电网[] []

I have a problem but can't seem to find anyone else that has tried to do a similar task. I have a grid of numbers in an int array 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

我需要一个简单的算法来找到哪里有只涨连接最号码，下，左，右。因此，在上面的例子中它会找到3在指数[2] [0]

I need a simple algorithm to find where there is the most numbers connected by only going up, down, left and right. So in the example above it would find the 3 at index [2][0].

我知道这个问题可以通过简单的if语句和循环循环之后做什么，但，这将是非常重复来解决，但不知道是否有这样做的更简单的方法？

I know the problem could be solved by simply doing if statement and loop after loop but that would be very repetitive but was wondering if there is an easier way of doing this?

任何帮助是AP preciated，这是一个游戏我创造。谢谢：）

Any help is appreciated, this is for a game I am creating. Thank you :)

编辑：帮助清除这个问题了。

to help clear this problem up.

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的答案，因为它会发现

the method would return 0,2 as the answer because it would find that

3
3 3 3
3 3

拥有最邻近的数

has the most adjacent numbers

另一示例中，

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

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

Thanks for all the answers so far, Depth first search looks interesting but can only find information on tree style searches so far.

推荐答案

也许这样的事情将与小的调整。我还没有运行它自己，但这个概念应该是清楚的。还可以优化因为相同的空间可以计算多次

Maybe something like this will work with small tweaks. I have not run it myself, but the concept should be clear. Can also be optimized since the same spaces may be evaluated multiple times.

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。

这篇关于爪哇 - 算法寻找最连接数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！