查找2D地图的无法到达的部分

Question

我不希望你为我解决这个问题,我只是想问一些想法.

这是下面的输入,它代表一张地图.'x'代表土地,而点 - 水.因此,使用'x',您可以在地图上表示"孤岛".

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地图,计算任何岛屿的开放状态,以及关闭的数量.

我再说一遍:我不想让你解决它,只需要一些吸气,解决的想法.谢谢

Answer 1

我认为使用好的旧洪水填充算法应该告诉你是否从某个角度来说你可以达到另一个点.

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

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