首页 > All-one Matrices
头像 xyq0220
发表于 2019-08-11 20:11:15
题意 给一个的01矩阵,找有多少个全1子矩阵不被其他全1子矩阵包括。 分析 用单调栈找到的全1子矩阵是不能向上扩展和向右扩展的,只需判断该子矩阵能否向左和向下扩展,若四个方向都不能扩展,则该矩阵合法。是否能向左扩展可用预处理出的左边一列的高度是否大于等于该子矩阵的高度判断,是否能向下扩展可用前缀和判 展开全文