All Tracks Algorithms Graphs Depth First Search Problem

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...
Your Rating:

Contributor

Notifications
View All Notifications

?