求助一道算法题。求思路。由一个 0 和 1 组成的矩阵，求出所有 1 构成的阶梯。

[letianqiu]

初步发现 size * (steps + 1) - steps = n，如果对于每一个元素都枚举一遍，感觉复杂度非常高，而且会重复，比如 size 为 2 的可能是 size 为 3 的其中一部分。求指导

[imn1]

原矩阵把 行 中连续的 1 保留，其他置为 0，得到新矩阵 A
原矩阵把 列 中连续的 1 保留，其他置为 0，得到新矩阵 B
AB 的交集（逻辑与）就是阶梯的角

后面自己推吧

[imn1]

楼上#21 说的不严谨，但原题也没有说清楚

#21 说的是 转角
还需要排除“断层”

[letianqiu]

@imn1 如果全都是 1 的矩阵，这么操作之后，并没有任何变化啊。要求就是 i 找出所有的形如图片中的台阶。觉得#18 说得有道理啊

[imn1]

@letianqiu
实际上我就是搞不清楚你原题中阶梯的定义
例如
11000
01000
01000
011111
这种是否也算阶梯

其实最简单的方法就是
把所有符合阶梯定义的图形都写出来，然后去矩阵中找交集（平移和竖移）
这里问题就是矩阵越大，那阶梯图形就越多，而且阶梯不明确定义横向最大连续和纵向最大连续的话，阶梯的变化很多

反正思路不应该是在矩阵中逐点“画”阶梯，而是把已知定义的阶梯整体在矩阵中匹配

[mrcn]

@shard 二维 dp 感觉可以做吧
只是想不出转移方程

[letianqiu]

@imn1 你给的这个例子不属于阶梯。阶梯必须是横向和纵向的长度相等。你的方法好高深。

[letianqiu]

@mrcn 对啊。对于状态转移方程这题完全没有思路。目前觉得#18 楼的方法比较可行。#21 的方法对我来说太过于高深了。大致能理解他的意思，但是完全驾驭不了

[victor97]

@letianqiu #20
满足一阶台阶且不满足二阶台阶的就是新台阶。
另外，不需要用 map，每个位置记录以它为结尾的所有阶梯就行。

[victor97]

@letianqiu #19
前缀和是快速判断某个区间全为 1 用的。
如果不用前缀和，每次判台阶的复杂度和是 size*step ；使用前缀和优化为 step。

[victor97]

@letianqiu
使用前缀和判断是否是新台阶的复杂度是常数级别的。

[letianqiu]

@victor97 大致明白了。受益匪浅啊。非常感谢啊。只是对于“另外，不需要用 map，每个位置记录以它为结尾的所有阶梯就行。”还有点点疑问。每个位置可能是不同 size 的阶梯的结尾，如果不开个 map 保存，如何能够记录。也许我没表达清楚题目要求，题目需要记录所有 size （宽度）下所有不同 steps （高度）的阶梯。所以我就想保存一个 map，key 是 size，value 还是一个 map，这个 map 的 key 是 steps，value 是阶梯的结尾位置的坐标。一个位置不可以出现在同一个 size 下，不同的高度的阶梯里。但是可以出现在不同的 size 的阶梯中。

[letianqiu]

@victor97 再次感谢你啊。按照你的思路，我基本上实现了。就是关于前缀和那一块没懂，我是用了五个 for 循环判断台阶的。比较傻

[Xs0ul]

@imn1 #23 拿已知定义匹配倒是和我想到一块儿去了，用卷积就行（