悬线法可以用来解决给定矩阵极大子矩阵问题。

洛谷 P4147 玉蟾宫

这题本质上就是给定一个矩阵，有一些格不能选，求能选的最大的子矩阵大小，可以用悬线法来解决。

悬线，指的是从某一点向上出发，不穿过任何障碍格的垂直线段。比如下图中的几条悬线：

有一个结论：最大子矩阵一定可以通过某条悬线向左右拓展而成（可能有多条可能的悬线）。其实这个结论也很好证明，因为矩阵一定是被框在边界或障碍物之间，那么拓展成这个矩阵的悬线就是到其下界在框它上面的障碍物的那条线，否则一定有更优的矩阵。

知道了这个，我们就可以枚举每一条悬线，求出它能拓展的最大矩阵求个 \(\max\)。由于只有 \(nm\) 条悬线，所以理论上是可以做到 \(O(nm)\) 的时间复杂度的。

接下来看具体操作。

悬线悬线，肯定要维护线的长度。记 \(up_{i,j}\) 为从 \((i,j)\) 出发的悬线的长度，则：若 \((i,j)\) 不为障碍物，则其为 \(up_{i-1,j}+1\)；否则为 \(0\)。这个很好理解，就是不是障碍物的话应该比上面的格子长度多 \(1\)。

接下来还需要知道悬线能拓展到哪里。线不好维护，那就先考虑点，然后“连点成线”：\(l_{i,j}\) 表示 \((i,j)\) 这个点能向左拓展的最长长度（包括本身），\(r_{i,j}\) 表示其能向右拓展的最长长度，转移和上面类似，如果 \((i,j)\) 不为障碍物则 \(l_{i,j}=l_{i,j-1}+1,r=r_{i,j+1}+1\)，否则均为 \(0\)。

这一部分的代码：

回到上面的话题，直接枚举四个点显然不可行，但是可以发现，当高/宽的两点确定之后（这里和下面的“高”/“宽”指的都是边而不是长度），另外两点也随之确定：它们之间的最“内”的障碍点（如果没有的话就是边界）。以确定高的两点为例：

上面的两个矩阵，就是分别以 \(1,2\) 和 \(3,4\) 为两条高的边界。注意到，这些点不一定在矩阵（指小矩阵）的边框上。

当然，其实情况还有一种，就是大矩阵的边界作为小矩阵的高，这点也得注意。

思路基本说明白了，但是实践到代码里还是会有不同，步骤如下（这里以确定高为例）（统一一下，下文的 \(n,m\) 指的是题目中的 \(W,L\)（宽和长），\(s\) 指的是障碍点个数，\((x,y)\) 这个点默认指的是第 \(x\) 行第 \(y\) 列而不是第 \(x\) 列第 \(y\) 行）：

把所有障碍点（包括边界）按 \(y\) 排序；

枚举每个障碍点当作左边的高，向右延伸到每一个点，并在延伸过程中实时统计当前矩阵的“上界”和“下界”;

从右往左再扫一遍；

把所有障碍点按 \(x\) 排序，统计以边界为高的情况。