ruby - Chris Pine Ruby 第 10 章，递归

Question

我一直在尝试使用 Chris Pine 的《学习编程》一书来学习 Ruby。事实上，在阅读这本书时，直到第 10 章和所使用的示例时，我都感到很兴奋。现在，仅这一章及其示例就已经完全消除了我继续阅读这本书的所有兴奋。在这个例子中，我完全不知道它是如何尝试计算图 block 的，或者当该方法是使用 Continental_size world, x,y 的属性定义时，为什么他使用 world [y],[x]？我不确定这个例子中的递归是如何工作的。有人可以更深入地了解这个例子，了解作者实际上想要做什么吗？

M = 'land'
o = 'water'

world = [
  [o,o,o,o,o,M,o,o,o,o,o],
  [o,o,o,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

  if x < 0 or x > 10 or y < 0 or y > 10
    return 0
  end

  if world[y][x] != 'land'
    return 0
  end

  size = 1
  world [y][x] = 'counted land'

  size = size + continent_size(world, x-1, y-1)
  size = size + continent_size(world, x , y-1)
  size = size + continent_size(world, x+1, y-1)
  size = size + continent_size(world, x-1, y )
  size = size + continent_size(world, x+1, y )
  size = size + continent_size(world, x-1, y+1)
  size = size + continent_size(world, x , y+1)
  size = size + continent_size(world, x+1, y+1)
  size

end

puts continent_size(world, 5, 5)

Answer 1

这称为洪水填充。它所做的就是计算与初始起点相连的所有“土地”的大小。请注意，它并未计算所有“陆地”符号，仅计算因水而无法到达的符号。

洪水填充是一种称为深度优先搜索的形式，它是一种遍历图形(此处为离散“ map ”)的方法。可以概括如下:

1. 访问当前位置/图节点，对其进行计数并将其标记为已访问
2. 检查所有连接的节点(这里是上、下、左、右的任何节点)，如果没有被访问并且是陆地，则递归访问它们

他可能出于以下原因执行 y, x:二维数组的逻辑格式首先按行组织，然后按列组织。可以将行视为 y 轴，将列视为 x 轴。