我如何在 APL 中标记连通组件？

Question

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我正在尝试解决LeetCode难题https://leetcode.com/problems/max-area-of-island/，需要对连通（通过边缘而非角落）的组件进行标记。

我该如何转换以下内容：

0 0 1 0 0
0 0 0 0 0
0 1 1 0 1
0 1 0 0 1
0 1 0 0 1

进入

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

我已经尝试使用模板⌺运算符和扫描运算符，但还没有完全达到目标。有人可以帮忙吗？

- mazin

---

嗨，我为代码挑战做了类似的事情 https://github.com/rak1507/Advent-Of-Code-APL/blob/main/2021/Day09.dyalog，也许那可以帮到你？{(×⍵)×⍵⌈⊃⌈/0 shifts ⍵}⍣≡{(1+⍳+/,⍵)@⊢⍵} - rak1507

Answer 1

我们可以从枚举数字开始。通过应用函数⍸（它会返回索引值），我们将其应用于子集掩码⊢所标识的位，即⍸@⊢（由于所有数都是1，所以等同于1、2、3…）:

      ⍸@⊢m
0 0 1 0 0
0 0 0 0 0
0 2 3 0 4
0 5 0 0 6
0 7 0 0 8

现在我们需要对每个组件中的最小数字进行洪泛填充。我们重复应用处理Moore邻域⌺3 3直到处理的von Neumann邻居的不动点 ⍣≡。为了得到von Neumann邻居，我们将Moore邻域中的9个元素重新塑形为一个4行2列的矩阵，并使用4 2⍴选择正确的列，然后使用⊢/。我们使用0~⍨移除任何0，并在原始值⍵[2;2]（即使为0）前加上,，然后使用⌊/选取最小值：

        {⌊/⍵[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

我们通过在矩阵的所有唯一元素中查找其⊢索引 ⍳⍨，再加上0后跟随着拉平后的矩阵,，来将值映射到索引上。

        (⊢⍳⍨∘∪0,,){⌊/⍵[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+(⊢⍳⍨∘∪0,,){⌊/⍵[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

- Adám

---

不错。我以前没见过(⍳+/)@⊢m。如果您能简要注释一下会很好，4 2⍴在这里是做什么的，看起来像个聪明的技巧，但不清楚它的作用。 - mazin

@AdamNathan 我插入了一些解释，尽管 (⍳+/) 在全为1的向量上非常愚蠢，所以我对此进行了简化。 - Adám

谢谢。使用最大值而不是过滤0是否会更简单？ - mazin

@AdamNathan 你可以使用max而不是min，但你仍然必须防止0的值从非0邻居处获取，因此你必须乘以当前值的符号或类似的东西：¯1+(∪⍤,⍳⊢){⍵[2;2](×⍤⊣×⌈/⍤,)⊢/4 2⍴⍵}⌺3 3⍣≡⍸@⊢m - Adám

再次审查后，我注意到当左上角不是背景时会出现问题。你会如何解决这个问题？排序(∪⍤,⍳⊢)看起来有点丑。 - mazin

发现得好。已修复。 - Adám