1

我有一个问题,我确信那里可能已经有很多有效的解决方案。为简化起见,我们假设网格宽度的单元格有两种类型的单元格,“X”单元格和“o”单元格。

 5 +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|X|X|o|o|o|o|o|X
 4 +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|o|o|X|o|o|o|o|o|X
 3 +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|X|X|X|o|o|X|o|o|X
 2 +-+-+-+-+-+-+-+-+-+-+-+
   |X|o|o|X|X|X|X|X|X|o|X
 1 +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|o|X|X|X|o|o|o|X 
   +-+-+-+-+-+-+-+-+-+-+-+
 0   1 2 3 4 5 6 7 8

现在正在选择“X”单元格之一。

   +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|X|X|o|o|o|o|o|X
   +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|o|o|X|o|o|o|o|o|X
   +-+-+-+-\-/-+-+-+-+-+-+
   |o|X|X|X<*>o|o|X|o|o|X
   +-+-+-+-/-\-+-+-+-+-+-+
   |X|o|o|X|X|X|X|X|X|o|X
   +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|o|X|X|X|o|o|o|X 
   +-+-+-+-+-+-+-+-+-+-+-+

我需要找出所选单元格所在的“X”覆盖区域的所有相邻“X”单元格。不直接连接并由组中的“o”单元格分隔的“X”单元格被排除在外。见下图。

   +.+.+-+.+.+-+-+-+-+-+-+
   :   :o:   :o|o|o|o|o|X
   +.+ +-+.+ +-+-+-+-+-+-+
   |o: :o|o: :o|o|o|o|o|X
   +-+ +.+.+ +-+-+.+-+-+-+
   |o:       :o|o: :o|o|X
   +-+.+.     .+.+ +.+-+-+
   |X|o|o:           |o|X
   +-+-+-+.+     +.+.+-+-+
   |X|X|o|o:     :o|o|o|X 
   +-+-+-+-+.+.+.+-+-+-+-+

基本上它是一个简单的“填充”功能,我需要在其中找到要填充的区域的边界。我确信这种东西甚至存在一个特定的名称。告诉我这也将不胜感激:)

4

1 回答 1

1

您所追求的算法的名称是Flood Fill。我有一个用于Pacman clone的简短代码示例(在F#中) 。

于 2014-06-04T18:24:44.950 回答