AT_abc410_f.[ABC410F] Balanced Rectangles

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

形式化地，求满足以下条件的整数四元组 $(u,d,l,r)$ 的个数：

$1\le u\le d\le H$
$1\le l\le r\le W$
$\sum\limits_{i=u}^d\sum\limits_{j=l}^r[S_{i,j}=$ # $]=\sum\limits_{i=u}^d\sum\limits_{j=l}^r[S_{i,j}=$ . $]$

输入格式

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

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

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

输出格式

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

输入输出样例

输入#1

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

输出#1

4
79
4032

说明/提示

样例解释

样例包含三组测试数据。

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

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

By @chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页