java - 贪心递归搜索

Question

我的教授给了我们一个任务，我需要在网格中的给定点周围搜索构成一个组的所有其他点(在这个例子中，我需要找到在“L”形中的点的数量问题)。

所以网格是 10x10，我的教授给了我们一个起点。我的教授给了我们一个想法，即检查相邻的点，并将其添加到一个集合中，如果该点是新发现的(将在集合中)，则递归调用该方法。

private Spot findSpots(Set<Spot> spots, Set<Spot> activeSpots, Spot initial) {
    Spot newSpot = null;


    Set<Spot> activeSet = new HashSet<Spot>();
    checkAround(activeSet, new Spot(initial.i - 1, initial.j));
    checkAround(activeSet, new Spot(initial.i + 1, initial.j));
    checkAround(activeSet, new Spot(initial.i, initial.j - 1));
    checkAround(activeSet, new Spot(initial.i, initial.j + 1));


    for (Spot spot : activeSet) {
        newSpot = findSpots(spots, activeSpots, spot);
        if (grid[newSpot.i][newSpot.j] == true)
            spots.add(newSpot);
    }

    return newSpot;
 }
 private boolean checkAround(Set<Spot> spots, Spot spot) {
    if (!spots.contains(spot)) {
        spots.add(spot);
        return true;
    }
    return false;
 }

我知道我需要一个边界条件(否则我会得到 stackoverflow 异常)，但我需要逻辑方面的帮助。

Answer 1

I know I need a boundary condition [...]

你自己说的。一个关键词是边界。您需要检查网格中的某个点是否合法，如果没有，就停止探索。

另一个停止条件是该地点是否已被访问。

如果你实现这两个停止条件，如果您在进行进一步的递归调用之前执行这些检查，你会找到一个不会溢出堆栈的解决方案。

像这样:

private int countSpots(Set<Spot> visited, Spot spot) {
    if (!isValid(spot) || visited.contains(spot)) {
        return 0;
    }

    visited.add(spot);

    int count = 1;
    count += countSpots(visited, new Spot(spot.x - 1, spot.y));
    count += countSpots(visited, new Spot(spot.x + 1, spot.y));
    count += countSpots(visited, new Spot(spot.x, spot.y + 1));
    count += countSpots(visited, new Spot(spot.x, spot.y - 1));
    return count;
}

顺便说一句，您使用的算法是 flood fill 的变体,在维基百科页面中查看更多信息和提示。