← 返回题目列表

AtCoder · abc410_f

I. 平衡矩形

中文机器翻译题面 查看原题

分数: 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 列