分数: 525 点
问题陈述
你被给予 H \times W 网格,其中每个单元格包含 # or ..
每个单元格中写入的符号信息如下 H 字符串 S_1,S_2,\dots,S_H 长度 W,其中的单元格 i从顶部开始的第行和 j从左边算起的第 列包含与 j- 第一个字符 S_i.
找出该网格中满足以下所有条件的矩形区域的数量:
- 包含的单元格数量
#和包含的单元格数量 矩形区域中的.相等。
形式上,求整数四元组的个数 (u,d,l,r) 满足以下所有条件:
- 1 \le u \le d \le H
- 1 \le l \le r \le W
- 从网格中提取部分网格时 u-th 至 d从上往下数第 l-th 至 r- 从左边算起,包含的单元格数
提取部分中的
#和包含的单元格数量 矩形区域中的.是相等的。
你被给予 T 测试用例。找出每个问题的答案。
约束
- 1 \le T \le 25000
- 1 \le H,W
- 总和 H \times W 一次输入中的所有测试用例不超过 3 \times 10^5.
- S_i 是一个长度为 W 组成
#和..
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。 每个测试用例均按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 2 ## #. .. 6 6 ..#... ..#..# #.#.#. .###.. ###### .###.. 15 50 .......................#...........###.###.###.### ....................#..#..#..........#.#.#...#.#.. .................#...#####...#.....###.#.#.###.### ..................#..##.##..#......#...#.#.#.....# ...................#########.......###.###.###.### ....................#.....#....................... .###........##......#.....#..#...#.####.####.##..# #..#.........#......#.....#..#...#.#....#....##..# #..#.........#......#.....#..#...#.#....#....##..# #.....##...###..##..#.....#..#...#.#....#....#.#.# #....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.# #....#..#.#..#.####.#....##..#...#.#....#....#.#.# #....#..#.#..#.#....#.....#..#...#.#....#....#..## #..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..## .##...##...####.##...####..#..###..####.####.#..##
示例输出 1
4 79 4032
该输入包含 3 测试用例。
对于 1st案例,如下 4 矩形区域满足问题陈述中的条件:
- 从 1st 至 2从顶部开始,从 2到 2左起第 2 列
- 从 2到 3从上往下数第 rd 行 1st 至 1左起第 3 列
- 从 2到 2从顶部开始,从 1st 至 2左起第 2 列
- 从 1st 至 3从上往下数第 rd 行 1st 至 2左起第 2 列