为N×M矩阵穿越
我与我的算法以下问题挣扎。 值'X'总是以矩形岛的形式出现,这些岛 总是按行和按列分隔至少一行'O'。 计算给定矩阵中的岛数。为N×M矩阵穿越
我已经生成了一个解决方案,但是我的循环没有通过整个矩阵。我试图在i循环中将j初始化为0,但是会引发错误。我对这个主题很陌生,我很想试着理解为什么我的代码无法正常工作。
def matrix(input)
row = input.length
col = input[0].length
counter = 0
i = 0
j = 0
while i < row do
while j < col do
if input[i][j] == "X"
if i == 0 || input[i-1][j] == "O" && j = 0 || input[i][j-1] == "O"
counter += 1
end
end
j += 1
end
i += 1
end
p counter
end
matrix(
[
["X", "X", "O", "X"],
["X", "X", "O", "X"],
["O", "O", "X", "O"],
["O", "O", "X", "O"],
["O", "O", "O", "X"],
["O", "O", "O", "X"]
]
)
# expected output is 4
这不是作业。我正在练习数据结构和算法。原来的问题,可以发现here
算法
我们给出称为“行”大小相等的数组的数组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很大学会理解这两种方法我介绍的工作。熟悉需要用下面的方法:
- 在模块Enumerable:
each_with_index
,any?
,find
,map
,product
- 在Enumerator类:
each_index
,with_object
,next
- 类Array:
pop
,sort
- 课次Integer:
abs
在模块
Kernel
- :
nil?
(在Object记载)
的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]
是在相同列中并且在相同行一列隔开分开或一列。
感谢您花时间解释。我被卡在迭代组数组的部分,以找到“岛”。从理论上讲,我明白你是如何得到剩余的4个组的,我只是不太明白你是如何实现逻辑 –
娜塔莎,我已经做了一些编辑(并做了一次更正,用'product'替换'zip')。这有助于你理解这些方法的工作原理吗? –
它没有经过完整的矩阵,因为在第一次迭代期间'j'值变为'4',一旦它达到那个值,'while j
@Gerry所以如果j-while循环从未被执行,那么我需要在该行之前初始化j = 0。这就是我所假设的... –
@Gerry我试了下面,并得到了8为输出def矩阵(输入) row = input.length col = input [0] .length counter = 0 i = 0 if i