简单递归算法中终止路径的问题

Question

首先：这不是一项家庭作业，而是我的一个爱好项目。

背景： 对于我的 Java 益智游戏，我使用一个非常简单的递归算法来检查“地图”上的某些空间在放置一块后是否已被隔离。在这种情况下，隔离意味着：不能放置任何棋子。

当前算法：

public int isolatedSpace(Tile currentTile, int currentSpace){
        if(currentTile != null){
            if(currentTile.isOpen()){
                currentTile.flag(); // mark as visited
                currentSpace += 1;
                currentSpace = isolatedSpace(currentTile.rightNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.underNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.leftNeighbor(),currentSpace);
                currentSpace = isolatedSpace(currentTile.upperNeighbor(),currentSpace);
                if(currentSpace < 3){currentTile.markAsIsolated();} // <-- the problem
            }
        }
        return currentSpace;
    }

这段代码返回起始图块所在的空白空间的大小。这部分代码按预期工作。但我遇到了一个关于瓷砖标记的问题，这就是这个问题的标题相关的原因；）

问题： 问题是某些图块永远不会被“重新访问”（它们返回一个值并终止，因此永远不会从后来的化身中获得返回值来更新空白空间的大小）。这些“被遗忘”的图块可能是大空间的一部分，但仍被标记为隔离，因为它们是在进程开始时 currentSpace 具有较低值时被访问的。

问题： 如何改进此代码，以便在没有太多开销的情况下为图块设置正确的值？我可以想到丑陋的解决方案，例如重新访问所有标记的图块，以及它们是否具有正确的值，检查邻居是否具有相同的值，如果没有更新等。但我确信 Stack Overflow 上有很多聪明的人有更好的想法； ）

---

更新： 我做了一些改变。

public int isolatedSpace(Tile currentTile, int currentSpace, LinkedList<Tile> visitedTiles){
        if(currentTile != null){
            if(currentTile.isOpen()){
                // do the same as before
                visitedTiles.add(); 
            }
        }
        return currentSpace;
    }

而marktiles函数（仅当返回的spacesize小于给定值时调用）

marktiles(visitedTiles){
       for(Tile t : visitedTiles){
            t.markAsIsolated();
       }
}

这种方法符合Rex Kerr的答案，至少如果我理解他的想法的话。

Answer 1

这不是通用解决方案，但只有当空格出现在两个或更少空格的区域中时，您才将它们标记为隔离的。难道您不能将此测试简化为“一个空间是孤立的，当且仅当（a）它没有开放邻居或（b）恰好有一个开放邻居并且该邻居没有其他开放邻居”。

Answer 2

您需要有一个两步过程：收集有关空间是否隔离的信息，然后单独标记为隔离。因此，您需要首先计算所有空间（使用一个递归函数），然后在标准通过时标记所有连接的空间（使用不同的递归函数）。