c++题：L形图表.
题目难度：中阶 时间限制：2000ms 内存限制：256mb
题目描述
给你一个N行M列的表格，表格上面每个格子都填上了 1 或 0。
当同一行或者同一列的某段连续格子都填了 1 的话，称这段连续的序列为优秀序列。
现在，你需要找出表格中存在的同时满足以下几个条件的 "L形图案"：
· 图案由两段连续格子构成，这两段连续的格子都必须是优秀序列；
· 图案中两段优秀序列相互垂直；
· 有一个格子属于两段优秀序列共同的末端端点；
· 选取的优秀序列必须长度至少为2；
· 较长的优秀序列长度必须刚好为较短的优秀序列长度的2倍。
· 你需要统计出给定的表格中，有多少个这样的 "L形图案"。
以下是 "L形图案" 的两个正确示例：
以及三个错误示例：
输入格式
第一行一个整数T, 表示共有T组数据
接下来的每组数据：
第1行两个整数N,M，对应表格的行数和列数
第2行~第N+1行，每行M个整数，表示表格中填写的数字
输出格式
输出T行，每行对应一组数据的答案
样例数据
输入数据
2
4 3
1 0 0
1 0 1
1 0 0
1 1 0
6 4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 1 0
1 0 1 0
1 1 1 0
输出数据
1
9
样例说明
样例一解释：
样例二解释：
样例二中有9个符合条件的 "L形图案"。
· 第1个: (1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (6,2), (6,3)
· 第2个: (3,1), (4,1), (5,1), (6,1), (6,2)
· 第3个: (6,1), (5,1), (4,1), (3,1), (3,2)
· 第4个: (3,3), (4,3), (5,3), (6,3), (6,2)
· 第5个: (6,3), (5,3), (4,3), (3,3), (3,2)
· 第6个: (3,1), (3,2), (3,3), (3,4), (2,4)
· 第7个: (3,4), (3,3), (3,2), (3,1), (2,1)
· 第8个: (3,4), (3,3), (3,2), (3,1), (4,1)
· 第9个: (6,3), (5,3), (4,3), (3,3), (3,4)
给出前3个 "L形图案" 对应的示意图：
数据范围
对于33%的数据，1<=N,M<=40;
对于66%的数据，1<=N,M<=100;
对于100%的数据，1<=N,M<=1000，1<=T<=10。
【相关推荐】
- 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7659378
- 除此之外, 这篇博客: Educational Codeforces Round 102 (Rated for Div. 2)中的 思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+±-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。但是题目要删掉，中间一段，剩下两段，也就是要把两段合并起来。画个图其实更好理解。红色的是所有的操作，绿色的是要删除的操作，第二个曲线就是合并之后的x值变化曲线。由图可知。后面那部分合并过来之后，起点就是前面那部分的终点！这就是关键点。然后前面那部分的区间的最大最小值和当前值都很好维护。难的是后面那部分怎么维护。后面那部分，从后往前维护，每到一个点，都认为这个点是零点，然后计算最大值最小值。因为是反着来，可以发现操作曲线是一个与 原操作 关于x轴对称的曲线，所以最大值就是最小值，最小值就是最大值。然后最小值就是 当前点到最小值的距离，最大值就是 当前点到最大值的距离。之所以算距离，是因为，永远认为当前点是0点。所以 距离 才是真正的最大最小值。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^