algorithm - 通常用于连通性的定义是什么

Question

我正在练习面试，我在 Glassdoor 上发现了以下问题。

Given a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black. An example given is
0 0 0 0 0 
0 1 1 1 0 
0 1 1 0 0 
0 1 0 0 0 
0 0 0 0 0

这个问题挑战了我对连通性的理解，下面矩阵中的1会不会被认为是相互连通的？

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

我应该默认考虑 8 连通性吗？

Answer 1

我应该默认考虑 8 连通性吗？

没有，connectivity 可以定义为 4 connected 和 8 connected 两种方式，并且没有默认的 connectivity 定义。此外，面试问题大多被低估了，因此您必须与面试官澄清，以防出现歧义。

找到包含全黑的最小矩形。

您可以用 -Infinity 替换所有的，然后使用 Kadane 的二维数组算法找到具有最大和的子矩形。在应用 kadane 之前，您还必须将零替换为零。对于实现 see this .

注意，无论黑色是否全部连通，寻找包含全0的最大子矩形的算法都是一样的。