algorithm - 使用递归方法查找接近路径或区域

Question

我在二维数组中有一个对象，我想遍历它们的顶部、左侧、右侧，实际上我想检查是否有一些循环或更好地制作一些封闭区域。请参阅此图片以获得更好的解释。

实际上我有一个 X x Y 的插槽，当用户触摸任何区域时，它会在那里添加砖 block ，所以我想做的是每次用户添加砖 block 时检查它是否正在形成闭合路径。

我已经为此编写了递归函数，但它工作不正常，它总是只针对顶部而不是左右。这是代码

function checkTrap(y,x)

if all_tiles[y][x].state == "changed" then --if brick is added at that location

 last_move_y = y
 last_move_x = x

  --check for top
  y = y - 1
  if( y >= 1 and y <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
    print("Moved to top at"..y..", "..x)
    return checkTrap(y, x)
  end
  --check for bottom
  y = y + 1
  if( y >= 1 and y <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
    print("Moved to bottom at"..y..", "..x)
    return checkTrap(y, x)
  end
  --check for left
  x = x - 1
  if( x >= 1 and x <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
    print("Moved to left at"..y..", "..x)
    return checkTrap(y, x)
  end
  --check for right
  x = x + 1
  if( x >= 1 and x <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
    print("Moved to right at"..y..", "..x)
    return checkTrap(y, x)
  end        

elseif all_tiles[y][x] == object then
  print("it's a loop"..y..", "..x)
  return true;

else
  print("not changed")
  return false
end

end

编辑:新解决方案

function findClosedRegion()
              local currFlag,  isClose = -1, false

              local isVisited = {
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1}}


              local k, m = 1, 1

              while k <= 6 and not isClose
              do
                print("K "..k)
                while m <= 6 and not isClose
                do
                  print("M "..m)
                  if not isBrick[k][m] and isVisited[k][m] == -1 then

                  local cellsi = Stack:Create()
                  local cellsj = Stack:Create()

                    cellsi:push(k)
                    print("Pushed k "..k)

                    cellsj:push(m)
                    print("Pushed m "..m)

                    currFlag = currFlag + 1
                    isClose = true

                    while cellsi:getn() > 0 and isClose do

                      local p = cellsi:pop()
                      print("Pop p "..p)

                      local q = cellsj:pop()
                      print("Pop q "..q)

                      if( p >= 1 and p <= 6 and q >= 1 and q <= 6 ) then
                        if(not isBrick[p][q]) then
                          print("white ")
                          if(isVisited[p][q] == -1) then
                            print("invisited")
                            isVisited[p][q] = currFlag

                             cellsi.push(p - 1)
                             cellsj.push(q)

                             cellsi.push(p + 1)
                             cellsj.push(q)

                             cellsi.push(p)
                             cellsj.push(q + 1)

                             cellsi.push(p)
                             cellsj.push(q - 1)

                            cellsi:list()
                          else
                            if(isVisited[p][q] < currFlag) then
                              print("visited < currFlag")
                              isClose = false
                            end
                          end
                        end
                      else
                        isClose = false
                      end --p and q if ends here
                    end -- tile while end
                  else
                  --print("changed and not -1")
                  end
                  m = m + 1
                end -- m while end
                if(isClose) then
                  print("Closed path")
                end
                m = 1
                k = k + 1
              end -- k while end
            end

Answer 1

实现的结构不会递归到其他方向，因为只调用了第一个分支；不知何故所有邻居都应该包括在内。显然你试图实现一种 Deph-first search在你的阵列上。该方法似乎绝对正确，但必须考虑单元格的所有邻居。可能最有帮助的是进行连通分量分析并填充接触边界的所有连通分量。