Expand the Pond

#1

help me to solve below q (cpp soln is must)

You are given a matrix with N rows and M columns. Each cell is either dry or has water. We say that two cells are neighbours if they share one of their four sides. A pond is a maximal subset of cells containing water such that any cell is accessible from any other cell by moving only along neighbours. You should add water to exactly one cell in order to maximise the size of the pond.
Input Format

The first line contains two integers N and M. Each of the next N lines contains M integers: 0 for a dry cell and 1 for a cell containing water.
Constraints

1 ≤ N,M ≤ 1000 There is at least one dry cell and one cell filled with water in the matrix.
Output Format

Print a single integer representing the largest possible size of the pond.
Sample Input

3 3
0 1 1
0 0 1
0 1 0

Sample Output

5

Explanation

Watering the cell at coordinates [2,2] unites the 2 ponds with sizes 1 and 3, resulting a pond of size 5, including the newly watered cell.

#2

Hey @Kash-Moulik-3715574511847721 run a DFS and make a Union of connected 1’s and give them unique I’d after that check for each zero that if it’s four side has different I’d one’s add the size of different union and store the maximum, this algorithm will run in O(n m) so it will not give tle, your algorithm is taking k n*m time where k is number of zero

#3

OK BUT IF U GIVE A CPP SOLN IT WILL BE BETTER TO HELP ME UNDERSTAND UR WORDS

#4

Here’s the code for same