/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
H 行 W 列のマス目があります。このマス目の上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
マス目の各マスは白または黒に塗られており、S_i の j 文字目が . のときマス (i, j) は白く、# のときマス (i, j) は黒く塗られています。
あなたは、以下の操作を高々 1 回行うことができます。
- ある矩形領域を 1 つ選び、その領域内のマスをすべて黒く塗る。より形式的には、1 \leq h_1 \leq h_2 \leq H かつ 1 \leq w_1 \leq w_2 \leq W を満たす整数 h_1, h_2, w_1, w_2 を選び、h_1 \leq h \leq h_2 かつ w_1 \leq w \leq w_2 を満たすすべての整数組 (h, w) に対し、マス (h, w) を黒く塗る。
得られるマス目の状態として考えられるものの個数を求めてください。ただし、2 つのマス目の状態は、1 \leq i \leq H, 1 \leq j \leq W を満たすある整数組 (i, j) が存在し、一方の状態ではマス (i, j) が白く塗られており、もう一方の状態ではマス (i, j) が黒く塗られているときに異なるものとします。
制約
- 1 \leq H, W
- H \times W \leq 2 \times 10^5
- H, W は整数
- S_i は
.,#からなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
答えを出力せよ。
入力例 1
2 3 #.. .##
出力例 1
7
高々 1 回の操作を行って得られるマス目の状態として考えられるものは、以下の 7 通りです。
#.. ##. #.# ### #.. ##. ### .## .## .## .## ### ### ###
入力例 2
4 1 # # # #
出力例 2
1
入力例 3
5 5 ..##. ..#.# .##.# ....# ##.##
出力例 3
96
Score : 525 points
Problem Statement
There is a grid with H rows and W columns. Let the cell at the i-th row from the top and j-th column from the left be denoted as cell (i, j).
Each cell of the grid is painted white or black: cell (i, j) is white if the j-th character of S_i is ., and black if it is #.
You can perform the following operation at most once.
- Choose a rectangular region, and paint all cells within that region black. More formally, choose integers h_1, h_2, w_1, w_2 satisfying 1 \leq h_1 \leq h_2 \leq H and 1 \leq w_1 \leq w_2 \leq W, and paint cell (h, w) black for every pair of integers (h, w) satisfying h_1 \leq h \leq h_2 and w_1 \leq w \leq w_2.
Find the number of possible states of the grid that can be obtained. Here, two states of the grid are considered different if there exists a pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W such that cell (i, j) is painted white in one state and painted black in the other state.
Constraints
- 1 \leq H, W
- H \times W \leq 2 \times 10^5
- 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
2 3 #.. .##
Sample Output 1
7
The possible states of the grid obtainable by performing the operation at most once are the following seven:
#.. ##. #.# ### #.. ##. ### .## .## .## .## ### ### ###
Sample Input 2
4 1 # # # #
Sample Output 2
1
Sample Input 3
5 5 ..##. ..#.# .##.# ....# ##.##
Sample Output 3
96