/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
H 行 W 列のグリッドがあります。このグリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは白または黒で塗られています。グリッドの情報は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって与えられ、S_i の j 文字目が . のときマス (i, j) は白で、S_i の j 文字目が # のときマス (i, j) は黒で塗られています。
グリッドの長方形領域であって、点対称に塗られているものの個数を求めてください。
より形式的には、以下の条件をすべて満たす整数の組 (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
- h_1 \leq i \leq h_2 かつ w_1 \leq j \leq w_2 を満たすすべての整数 i, j についてマス (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
Score : 200 points
Problem Statement
There is a grid with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i, j).
Each cell of the grid is colored white or black. The information of the grid is given by H strings S_1, S_2, \ldots, S_H each of length W: cell (i, j) is white if the j-th character of S_i is ., and black if it is #.
Find the number of rectangular regions of the grid that are point-symmetrically colored.
More formally, find the number of integer tuples (h_1, h_2, w_1, w_2) satisfying all of the following conditions:
- 1 \leq h_1 \leq h_2 \leq H
- 1 \leq w_1 \leq w_2 \leq W
- For all integers i, j satisfying h_1 \leq i \leq h_2 and w_1 \leq j \leq w_2, cell (i, j) and cell (h_1 + h_2 - i, w_1 + w_2 - j) have the same color.
Constraints
- 1 \leq H, W \leq 10
- H and W are integers.
- S_i is a string of length W consisting of
.and#.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Output the answer.
Sample Input 1
3 2 .# #. ##
Sample Output 1
10
As shown in the figure above, the answer is 10.
Sample Input 2
4 5 .#.#. ####. ##..# ....#
Sample Output 2
54