#aising2019c. [aising2019_c]Alternating Path
[aising2019_c]Alternating Path
Problem Statement
There is a grid with rows and columns, where each square is painted black or white.
You are given strings , each of length . If the square at the -th row from the top and the -th column from the left is painted black, the -th character in the string is #
; if that square is painted white, the -th character in the string is .
.
Find the number of pairs of a black square and a white square that satisfy the following condition:
- There is a path from the square to the square where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...
Constraints
- ()
- For each (), the string consists of characters
#
and.
.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
3 3
.#.
..#
#..
Sample Output 1
10
Some of the pairs satisfying the condition are and , where denotes the square at the -th row from the top and the -th column from the left.
Sample Input 2
2 4
....
....
Sample Output 2
0
Sample Input 3
4 3
###
###
...
###
Sample Output 3
6