/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
H \times W のグリッドが与えられ、各マスには # か . のどちらかが書かれています。
各マスに書かれている記号の情報は H 個の長さ W の文字列 S_1,S_2,\dots,S_H として与えられ、上から i 行目、左から j 列目にあるマスには S_i の j 文字目と同じ記号が書かれています。
このグリッドに対し、以下の条件を全て満たす長方領域がいくつあるか求めてください。
- 長方領域に含まれる
#が書かれたマスの個数と.が書かれたマスの個数が等しい。
厳密には、次の条件を全て満たす 4 つの整数の組 (u,d,l,r) の数を求めてください。
- 1 \le u \le d \le H
- 1 \le l \le r \le W
- グリッドのうち上から u 行目から d 行目、左から l 列目から 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 個のテストケースが含まれます。
1 番目のケースについて、以下の 4 個の長方領域が問題文中の条件を満たします。
- 上から 1 行目から 2 行目、左から 2 列目から 2 列目
- 上から 2 行目から 3 行目、左から 1 列目から 1 列目
- 上から 2 行目から 2 行目、左から 1 列目から 2 列目
- 上から 1 行目から 3 行目、左から 1 列目から 2 列目
Score : 525 points
Problem Statement
You are given an H \times W grid, where each cell contains # or ..
The information about the symbols written in each cell is given as H strings S_1,S_2,\dots,S_H of length W, where the cell in the i-th row from the top and j-th column from the left contains the same symbol as the j-th character of S_i.
Find the number of rectangular regions in this grid that satisfy all of the following conditions:
- The number of cells containing
#and the number of cells containing.in the rectangular region are equal.
Formally, find the number of quadruples of integers (u,d,l,r) that satisfy all of the following conditions:
- 1 \le u \le d \le H
- 1 \le l \le r \le W
- When extracting the part of the grid from the u-th through d-th rows from the top and from the l-th through r-th columns from the left, the number of cells containing
#and the number of cells containing.in the extracted part are equal.
You are given T test cases. Find the answer for each of them.
Constraints
- 1 \le T \le 25000
- 1 \le H,W
- The sum of H \times W over all test cases in one input does not exceed 3 \times 10^5.
- S_i is a string of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:
H W S_1 S_2 \vdots S_H
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 3 2 ## #. .. 6 6 ..#... ..#..# #.#.#. .###.. ###### .###.. 15 50 .......................#...........###.###.###.### ....................#..#..#..........#.#.#...#.#.. .................#...#####...#.....###.#.#.###.### ..................#..##.##..#......#...#.#.#.....# ...................#########.......###.###.###.### ....................#.....#....................... .###........##......#.....#..#...#.####.####.##..# #..#.........#......#.....#..#...#.#....#....##..# #..#.........#......#.....#..#...#.#....#....##..# #.....##...###..##..#.....#..#...#.#....#....#.#.# #....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.# #....#..#.#..#.####.#....##..#...#.#....#....#.#.# #....#..#.#..#.#....#.....#..#...#.#....#....#..## #..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..## .##...##...####.##...####..#..###..####.####.#..##
Sample Output 1
4 79 4032
This input contains 3 test cases.
For the 1st case, the following 4 rectangular regions satisfy the conditions in the problem statement:
- From the 1st to 2nd rows from the top, from the 2nd to 2nd columns from the left
- From the 2nd to 3rd rows from the top, from the 1st to 1st columns from the left
- From the 2nd to 2nd rows from the top, from the 1st to 2nd columns from the left
- From the 1st to 3rd rows from the top, from the 1st to 2nd columns from the left