← 返回题目列表

AtCoder · abc455_b

B. 螺旋星系

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

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