算法
我们给出称为“行”大小相等的数组的数组input。问题中给出的例子如下。
input = [
["X", "X", "O", "X"],
["X", "X", "O", "X"],
["O", "O", "X", "O"],
["O", "O", "X", "O"],
["O", "O", "O", "X"],
["O", "O", "O", "X"]
]
为方便起见，我将提到的元件input[3][2] #=> "X"作为元素在行3和柱2（即使Ruby没有二维阵列的或具有行和列阵列的概念） 。
的第一步是建立一个数组groups，每个元件由一个元件的（“组”），以“X”的行中的一个的索引：
groups
#=> [[[0, 0]], [[0, 1]], [[0, 3]], [[1, 0]], [[1, 1]], [[1, 3]],
# [[2, 2]], [[3, 2]], [[4, 3]], [[5, 3]]]
我们现在考虑groups（[[5, 3]]）的最后一个元素，并询问它的任何元素（是否只有一个，[5, 3]）与其他任何组中的元素都在同一个岛中。我们发现它与[[4, 3]]组中的[4, 3]位于同一个岛上（因为这些元素位于同一列中，相隔一行）。因此，我们删除最后一个组，并将其所有元素（这里只是一个）添加到组[[4, 3]]。我们现在有：
groups
#=> [[[0, 0]], [[0, 1]], [[0, 3]], [[1, 0]], [[1, 1]], [[1, 3]],
# [[2, 2]], [[3, 2]], [[4, 3], [5, 3]]]
我们现在重复与什么现在是最后一组，[[4, 3], [5, 3]]过程。我们必须确定该组中的任何一个元素是否与其他组中的任何元素位于同一个岛上。他们不是。因此，我们确定了第一个岛屿，其中包括[4, 3]和[5, 3]。所以现在
groups
#=>#=> [[[0, 0]], [[0, 1]], [[0, 3]], [[1, 0]], [[1, 1]], [[1, 3]],
# [[2, 2]], [[3, 2]]]
islands
#=> [[[4, 3], [5, 3]]]
我们继续这样，直到groups是空的，此时的islands每个元素是一个岛国
islands << groups.pop
：
初始化islands = []后，我们进行了以下操作。
代码
def find_islands(input)
groups = input.each_with_index.with_object([]) { |(row,i),groups|
row.each_with_index { |c,j| groups << [[i,j]] if c == 'X' } }
islands = []
while groups.any?
last_group = groups.pop
idx = groups.each_index.find { |idx| same_island?(groups[idx], last_group) }
if idx.nil?
islands << last_group
else
groups[idx] += last_group
end
end
islands.map(&:sort)
end
def same_island?(group1, group2)
group1.product(group2).any? { |(i1,j1),(i2,j2)|
((i1==i2) && (j1-j2).abs == 1) || ((j1==j2) && (i1-i2).abs == 1) }
end
例
对于阵列input给出上面我们得到岛下面的数组。
find_islands(input)
#=> [[[4, 3], [5, 3]],
# [[2, 2], [3, 2]],
# [[0, 3], [1, 3]],
# [[0, 0], [0, 1], [1, 0], [1, 1]]]
说明
有无可否认，一个没有经验的Rubiest很大学会理解这两种方法我介绍的工作。熟悉需要用下面的方法：
的groups
初始计算如果作出一个单独的方法（未尝不可），我们将编写以下。
def construct_initial_groups(input)
input.each_with_index.with_object([]) { |(row,i),groups|
row.each_with_index { |c,`j| groups << [[i,j]] if c == 'X' } }
end
Ruby的新手可能会发现这有点压倒性。事实上，这只是Ruby方法来收紧以下方法。
def construct_initial_groups(input)
groups = []
i = 0
input.each do |row|
j = 0
row.each do |c|
groups << [[i,j]] if c == 'X'
j += 1
end
i += 1
end
groups
end
从这里到达的第一步是使用方法Enumerable#each_with_index。
def construct_initial_groups(input)
groups = []
input.each_with_index do |row,i|
row.each_with_index do |c,j|
groups << [[i,j]] if c == 'X'
end
end
groups
end
接下来，我们使用该方法Enumerator#with_object以获得上述的construct_initial_groups第一种形式。
写入块变量（|(row,i),groups|）可能仍然令人困惑。您将了解
enum = input.each_with_index.with_object([])
#=> #<Enumerator: #<Enumerator: [["X", "X", "O", "X"], ["X", "X", "O", "X"],
# ["O", "O", "X", "O"], ["O", "O", "X", "O"], ["O", "O", "O", "X"],
# ["O", "O", "O", "X"]]:each_with_index>:with_object([])>
是枚举，其元素通过应用该方法Enumerator#next产生。
(row,i), groups = enum.next
#=> [[["X", "X", "O", "X"], 0], []]
红宝石使用消歧或分解将值分配给每三个块变量：
row
#=> ["X", "X", "O", "X"]
i #=> 0
groups
#=> []
我们然后执行块的计算。
row.each_with_index { |c,j| groups << [[i,j]] if c == 'X' }
#=> ["X", "X", "O", "X"].each_with_index { |c,j| groups << [[i,j]] if c == 'X' }
#=> ["X", "X", "O", "X"]
所以现在
groups
#=> [[[1, 0]], [[1, 1]], [[1, 3]]]
现在产生的enum第二元件，并传递到块并执行该块的计算。
(row,i), groups = enum.next
#=> [[["O", "O", "X", "O"], 2], [[[1, 0]], [[1, 1]], [[1, 3]]]]
row
#=> ["O", "O", "X", "O"]
i #=> 2
groups
#=> [[[1, 0]], [[1, 1]], [[1, 3]]]
row.each_with_index { |c,j| groups << [[i,j]] if c == 'X' }
#=> ["O", "O", "X", "O"]
现在groups有两个元素。
groups
#=> [[[1, 0]], [[1, 1]],
# [[1, 3]], [[2, 2]]]
其余的计算是类似的。
same_island? method
假设
group1 #=> [[0, 0], [1, 0]]
group2 #=> [[0, 1], [1, 1]]
这告诉我们，[0, 0]，[1, 0]都在同一个岛上和[0, 1]和[1, 1] areon同一个岛上，但我们不知道的还是否全部四个坐标在同一个岛上。要确定是否属于这种情况，我们将查看所有坐标对，其中一个来自group1，另一个来自group2。如果我们比较[0, 0]和[1, 1]，我们不能得出结论他们在同一个岛上（或不同的岛屿）。然而，当我们比较[0, 0]和[0, 1]时，我们看到它们在同一个岛上（因为它们在相邻列中位于同一行），所以我们推断两个组的所有元素都在同一个岛上。例如，我们可以将坐标从group2移动到group1，并从进一步的考虑中消除group2。
现在考虑这两个组的方法same_island?执行的步骤。
group1 = [[0, 0], [1, 0]]
group2 = [[0, 1], [1, 1]]
a = group1.product(group2)
#=> [[[0, 0], [0, 1]], [[0, 0], [1, 1]], [[1, 0], [0, 1]],
# [[1, 0], [1, 1]]]
(i1,j1),(i2,j2) = a.first
#=> [[0, 0], [0, 1]]
i1 #=> 0
j1 #=> 0
i2 #=> 0
j2 #=> 1
b = i1==i2 && (j1-j2).abs == 1
#=> true
c = j1==j2 && (i1-i2).abs == 1
#=> false
b || c
#=> true
第一对考虑的坐标被发现在同一个岛上。 （事实上，也不会因为b被认为是true执行c计算。）
find_islands评论
要显示一切是如何结合在一起，我会添加注释方法find_islands。
def find_islands(input)
groups = input.each_with_index.with_object([]) { |(row,i),groups|
row.each_with_index { |c,j| groups << [[i,j]] if c == 'X' } }
islands = []
# the following is the same as: until groups.empty?
while groups.any?
# pop removes and returns last element of `groups`. `groups` is modified
last_group = groups.pop
# iterate over indices of `groups` looking for one whose members
# are on the same island as last_group
idx = groups.each_index.find { |idx| same_island?(groups[idx], last_group) }
if idx.nil?
# last_group is an island, so append it to islands
islands << last_group
else
# groups[idx] members are found to be on the same island as last_group,
# so add last_group to group groups[idx]
groups[idx] += last_group
end
end
# sort coordinates in each island, to improve presentation
islands.map(&:sort)
end
1即，没有元件groups[i,j]为其中或者[4, 3]或[5, 3]是在相同列中并且在相同行一列隔开分开或一列。
2模块Kernel中的实例方法记录在类Object中。请参阅Kernel的前两段和Object的第二段。
它没有经过完整的矩阵，因为在第一次迭代期间'j'值变为'4'，一旦它达到那个值，'while j
Gerry
@Gerry所以如果j-while循环从未被执行，那么我需要在该行之前初始化j = 0。这就是我所假设的... –
@Gerry我试了下面，并得到了8为输出def矩阵（输入） row = input.length col = input [0] .length counter = 0 i = 0 if i