2D数组 - 检测位置是否在闭合图案内

Question

假设我有以下内容:

{ 0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,X,X,X,0,
  0,0,0,X,X,X,X,0,X,0,
  0,0,0,X,0,A,0,0,X,0,
  0,0,0,X,0,0,X,X,X,0,
  0,0,0,X,X,X,X,0,0,0,
  0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0 }

正如你所看到的,显然A在内部被所有X包围(对角线不计数).那么我可以检测数组中的一个点是否被X包围,它当然是关闭的吗？任何递归算法？我想到了以下伪代码:

bool IsSurroundedByX( Vector2 A )
{
     if A is an extrem from the matrix ( column is 0 or N-1 || row is 0 or M -1 ) and not an X return false
     if A is an X return true
     return IsSurroundedByX( A + left ) && 
            IsSurroundedByX( A + right ) && 
            IsSurroundedByX( A + bottom ) && 
            IsSurroundedByX( A + top ) && 
}

但我认为这不会起作用.

Answer 1

你快到了.

你的方法基本上是洪水填充 (如果DFS是一个变种),它可以工作,但你错过了一件小事 - 确保你的递归停止.

就目前而言,你将拥有无限循环,因为你允许left-right-left-right-left-right-....和这样的模式.

通过添加visitedset 可以轻松处理此问题.这个集合基本上是一组所有节点,如果你的递归到达你已经访问过的节点 - 它什么都不做.这将允许您最多遍历所有单元格一次(并避免无限循环).