I got a solution for this..in O(n*M) complexity..but I think this will be litttlebit confusing in implementation

#1

I firstly will find the max big pond I can make for a cell…and this I can do in O(nm) complexity and same extra space of O(nm)…and then I can just use simply greedy to find which pond to be filled…but I want to know another solution…which can be little bit different approach then mine…My exact explanation is this that…there will be 5 to 6 differnet or more ponds which can be connected by the single unfilled box…and that best box I am tying to find…and in the pond matrix I will give each filled cell a number that it belongs to pond no1 r pond no2 and so on…and I will make another dp matrix you can say…which will store the area of pond we can have for cells belonging to this pond…i.e a 1D array that for cells belonging to pond1 I have 45area…and for cells belonging to pond2 I have 30area…and so on …But I want to know another approach…if there is another one without DP…

#2

The approach can be as:
First we can use a flood fill algorithm to determine the black shapes and their sizes. Then we can take each white cell (there’s no point in changing the colour of a black cell) and see what happens if we choose it. We need to check its black neighbouring cells. We take the shapes of the black neighbours, being careful not to choose the same shape twice, and sum their sizes. The answer is the maximum of these sums plus 11 (for the white chosen cell).

#3

Actually I haven’t covered the flodfill algorithm…i.e the graph portion till now…but I think that will be an optimized approach …I just wanted to know with what approach they have implemented it…because I am not able to solve it with recursion only…I would need DP to solve it…

#4

They have solved with the same approach fusing floodfill algorithm .