SOLVE

LATER

Path

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 '`.'`

.

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

Initializing Code Editor...

{"c76dc41": "/pagelets/recommended-problems/algorithm/servers-of-nirma/", "93947dc": "/pagelets/show-submission/algorithm/servers-of-nirma/", "6859d13": "/pagelets/suggested-problems/algorithm/servers-of-nirma/", "faa947e": "/pagelets/problems-hint/algorithm/servers-of-nirma/", "ac7c837": "/pagelets/problem-author-tester/algorithm/servers-of-nirma/"}

realtime.hackerearth.com

80

c4181644737fd6fbaddbb303968161b2677e4d83

58a29e5cae2309f04b28

/realtime/pusher/auth/