如何在 APL 中标记连接的组件？

Question

我正在尝试做 leet puzzle https://leetcode.com/problems/max-area-of-island/，需要标记连接的（边，而不是角）组件。

我怎样才能转换像

这样的东西

进入

我玩过模板 ⌺ 运算符，也尝试过使用扫描运算符，但仍然不尽如人意。有人可以帮忙吗？

Answer 1

我们可以从列举这些开始。我们通过应用函数 ⍸ 来实现（其中，但是因为所有都是 1，所以它相当于 1,2,3,...）@ at由 ⊢ 位本身屏蔽的子集，即 ⍸@⊢:

现在我们需要淹没每个组件中的最小数字。我们通过重复应用来做到这一点，直到处理摩尔邻域 ⌺3 3 的固定点 ⍣≡。为了得到冯·诺依曼邻居，我们将 Moore 邻居中的 9 个元素重塑为一个 4 行 2 列的矩阵，其中 4 2⍴ 并使用 ⊢/ 到 select 右列。我们删除任何带有 0~⍨ 的 0，它们会在 , 原始值 ⍵[2;2] 之前加上 ⍵[2;2] （即使是 0），并具有 ⌊/ select 最小值：

        {⌊/⍵[2;2],0~⍨⊢/4 2⍴⍵}⌺3 3⍣≡⍸@⊢m
0 0 1 0 0
0 0 0 0 0
0 2 2 0 4
0 2 0 0 4
0 2 0 0 4

我们通过找到它们的 ⊢ 索引 ⍳ 拼合矩阵的唯一元素 ∪⍤⊢:

将值映射到索引

        (∪⍤,⍳⊢){⌊/⍵[2;2],0~⍨⊢/4 2⍴⍵}⌺3 3⍣≡⍸@⊢m
1 1 2 1 1
1 1 1 1 1
1 3 3 1 4
1 3 1 1 4
1 3 1 1 4

调整回从零开始的减量：

        ¯1+(∪⍤,⍳⊢){⌊/⍵[2;2],0~⍨⊢/4 2⍴⍵}⌺3 3⍣≡⍸@⊢m
0 0 1 0 0
0 0 0 0 0
0 2 2 0 3
0 2 0 0 3
0 2 0 0 3

如何在 APL 中标记连接的组件？

How can I label connected components in APL?

connected-components

apl

dyalog