algorithm - 查找二维 map 中无法到达的部分

Question

我不想让你为我解决这个问题，我只是想问一些想法。

这是下面的输入，代表一张 map 。 “x”代表土地，点代表水。因此，使用“x”，您可以在 map 上代表“岛屿”。

xxx.x...xxxxx        
xxxx....x...x        
........x.x.x        
..xxxxx.x...x       
..x...x.xxx.x        
..x.x.x...x..        
..x...x...xxx        
...xxxxxx....        
x............ 

如您所见，有些岛屿是封闭的，即如果有船只在其领土内，它将无法出海，例如:

..xxxxx.     
..x...x.        
..x.x.x.        
..x...x.
..xxxxx.

还有一些开放的岛屿是可以离开的，例如:

.xxxxx        
.x...x        
.x.x.x        
.xxx.x       

问题是这样的:对于像上面那些给定的 NxM map ，计算有多少岛屿是开放的，有多少岛屿是封闭的。

我再说一遍:我不想让你解决它，只需要一些建议，解决问题的想法。谢谢

Answer 1

我认为使用旧的洪水填充算法应该可以告诉您是否可以从某个点到达另一个点。

http://en.wikipedia.org/wiki/Flood_fill

此外，您可能需要更好地定义内部和外部的含义(我认为)。