点我进入原题提交页面

题目描述

给你一个 $H\times W$ 的网格 $S$，仅由 # 和 . 组成。

求其中有多少个矩形区域，其中 # 和 . 的个数相等。

输入格式

多组数据。第一行一个整数 $T(1\le T\le 2.5\times 10^4)$，表示数据组数。

对于每组数据：

• 第一行两个整数 $H,W$。
• 接下来 $H$ 行，每行一个长为 $W$ 的，由 # 和 . 组成的字符串 $S_i$。

保证单个测试点中，$\sum (HW)\le 3\times 10^5$。

输出格式

对于每组数据，输出一行一个整数表示答案。

3
3 2
##
#.
..
6 6
..#...
..#..#
#.#.#.
.###..
######
.###..
15 50
.......................#...........###.###.###.###
....................#..#..#..........#.#.#...#.#..
.................#...#####...#.....###.#.#.###.###
..................#..##.##..#......#...#.#.#.....#
...................#########.......###.###.###.###
....................#.....#.......................
.###........##......#.....#..#...#.####.####.##..#
#..#.........#......#.....#..#...#.#....#....##..#
#..#.........#......#.....#..#...#.#....#....##..#
#.....##...###..##..#.....#..#...#.#....#....#.#.#
#....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.#
#....#..#.#..#.####.#....##..#...#.#....#....#.#.#
#....#..#.#..#.#....#.....#..#...#.#....#....#..##
#..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..##
.##...##...####.##...####..#..###..####.####.#..##

4
79
4032

说明/提示

样例解释

样例包含三组测试数据。

对于第一组数据，满足条件的 $4$ 个四元组如下：

• $(1,2,2,2)$
• $(2,3,1,1)$
• $(2,2,1,2)$
• $(1,3,1,2)$