Path
Tag(s):

Medium

Problem
Editorial
Analytics

There is a grid with $H$ rows and $W$ columns, where each square is either black or white.

You are given $H$ strings $S_1,S_2,S_3\dots S_H$, each of length $W$. If the square at the $i^{th}$ row from the top and the $j^{th}$ column from the left is painted black, the $j^{th}$ character in the string $S_i$ is  "#"; if that square is painted white, the $j^{th}$character in the string $S_i$ is "." .

Find the number of pairs of a black square $c_1$ and a white square $c_2$that satisfy the following condition:

• There is a path from the square $c_1$ to the square $c_2$ where we repeatedly move up,down,right or left through an alternating sequence of black and white squares: black, white, black, white... and so on.

Constraints

• $1\leq H,W \leq 400$
• $|S_i|=W (1\leq i\leq H)$
• For each $i (1\leq i\leq H)$, the string $S_i$consists of characters '#' and '.' .
SAMPLE INPUT
3 3
.#.
..#
#..
SAMPLE OUTPUT
10

Explanation

Some of the pairs satisfying the condition are ($(1,2),(3,3)$ and $(3,1),(3,2)$, where$(i,j)$denotes the square at the $i^{th}$ row from the top and the $j^{th}$ column from the left.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...