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

首先：这不是一项家庭作业，它是我的一个爱好项目。简单递归算法中终止路径的问题

背景： 对于我的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; 
    }

这段代码返回空空间，其中起始瓦是其一部分的尺寸。这部分代码的工作原理如图所示。但是我碰到关于瓷砖的标志，这是什么使有关这个问题的标题一个问题就来了;）

问题： 的问题是，某些瓷砖从未“重新”（他们返回值和终止，所以从未从后来的化身中获得返回值来更新空白空间的大小）。这些“被遗忘”的瓷砖可以是大空间的一部分，但仍然被标记为孤立的，因为在当前空间具有较低值时在开始处访问它们。

问题： 如何改善这段代码，使它为瓷砖设置正确的值，而没有太多的开销？我可以想到丑陋的解决方案，如重新访问所有标记的瓦片，以及它们是否具有适当的值，检查邻居是否具有相同的值，如果不更新等。但我确信有堆栈溢出的人们有更好的想法; ）

更新： 我已经做了一些改动。

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(); 
     } 
}

这种做法与雷克斯克尔的答案线，至少如果我明白了他的理念。

来源

2010-08-19 Erik1984

另一方面，我想指出的是，根据所涉及的特定部分，即使大面积的形状不佳，也可能是“孤立的”。例如，如果您没有线性部分，则无法填充20个空格的线。如果那么重要，你可能不得不下放试图将每件作品放在每个位置/方向;标记任何有效位置覆盖的方块，然后完成标记反转以获得无用空间。 – 2010-08-20 15:44:56

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

来源

2010-08-20 13:57:22

感谢您的解决方案！你所描述的看起来就像我在此期间实施的一样。每个标记的图块现在都被添加到名为visitedTiles的列表中。在计算空间（并且最终大小已知）之后，称为markTiles的第二个函数（仅当空间的总大小小于某个值时）会将列出的图块标记为孤立。这似乎工作正常。 – Erik1984 2010-08-20 15:10:19

这不是一个通用的解决方案，但是如果它们出现在两个或更少空间的区域中，则只能将空间标记为孤立。难道你不能简化这个测试：“一个空间是孤立的，如果（a）它没有开放的邻居或者（b）恰好一个开放的邻居并且那个邻居没有其他开放的邻居”。

来源

2010-08-19 23:50:20 Rafe

这是个好主意，谢谢！然而，孤立空间的大小将随着拼图中使用的棋子而改变。碎片的形状各异，有三种尺寸：三块，四块，五块。因此，小于3块瓷砖的空间总是被隔离，但是当仅有四块或五块块可用时，小于4块瓷砖也成为隔离空间。 – Erik1984 2010-08-20 08:05:08

我认为可能是这种情况。这里有一个想法可能会让你的算法更加精简：为每个空间添加一个“空间ID”字段。当您放置或移除一块时，为该空间选择一个新的，新鲜的ID，并执行递归填充算法，用新ID标记每个连接的空间并跟踪已标记的空间数量。如果你的空间ID有足够的位（一个int很可能是好的，一个long可能是矫枉过正的），你不需要保留一个单独的访问过的tile的列表或者做一个单独的标记阶段。 – Rafe 2010-08-23 03:10:13

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

回答

相关问题