分数: 200 点
问题陈述
有一个网格 H 行和 W 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i, j).
网格的每个单元格都是白色或黑色。网格的信息由下式给出 H 字符串 S_1, S_2, \ldots, S_H 每个长度 W:细胞 (i, j) 为白色,如果 j- 第一个字符 S_i is .,如果是黑色 #.
查找网格中点对称着色的矩形区域的数量。
更正式地说,查找整数元组的数量 (h_1, h_2, w_1, w_2) 满足以下所有条件:
- 1 \leq h_1 \leq h_2 \leq H
- 1 \leq w_1 \leq w_2 \leq W
- 对于所有整数 i, j 满意 h_1 \leq i \leq h_2 和 w_1 \leq j \leq w_2,细胞 (i, j) 和细胞 (h_1 + h_2 - i, w_1 + w_2 - j) 具有相同的颜色。
约束
- 1 \leq H, W \leq 10
- H 和 W 是整数。
- S_i 是一个长度为的字符串 W 组成
.和#.
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
输出答案。
示例输入 1
3 2 .# #. ##
示例输出 1
10

如上图所示,答案是 10.
示例输入 2
4 5 .#.#. ####. ##..# ....#
示例输出 2
54