ruby - Chris Pine Ruby 第 10 章，递归

Question

我一直在尝试通过 Chris Pine 的“学习编程”一书来学习 ruby​​。在读到第 10 章和使用的示例之前，我真的很兴奋。现在，仅这一章及其示例就完全消除了我继续阅读本书的所有兴奋。在这个例子中，我完全不知道它是如何尝试计算瓷砖的，或者为什么他使用 world [y],[x] 当方法定义为 continent_size world, x,y 的属性时？我不确定这个例子中的递归是如何工作的。有人可以进一步阐明这个例子，说明作者实际上想做什么吗？

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。