算法
我們給出稱爲「行」大小相等的數組的數組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