In this problem first of all i grouped the already available ponds.
For example: Assume the matrix is:
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
so this matrix i transform into:
1 1 1 1
0 0 0 0
2 2 2 2
0 0 0 0
3 3 3 3
group 1 has 4 size i store this as well.
Similarly group 2 has size 4 and so does 3
After storing group number and size.
I run for loop and everytime i get a 0 i check for its boundaries i.e check for i+1, i-1, j+1, j-1 up,bottom,right,left cells. If those cells belong to a group say top cell is 1 i add dp[1] which contains size of the group 1 to my count, if bottom contains cell 2 i add dp[2]. I have checked that i do not add same group count twice, i maintained a set which stores already added groups to my count. I do this for every 0 and get the max answer.
For example consider index of 0 as 1,0 i check top i find that cell is 1 so i add dp[1] then i check the cell below i find that it is 2 so i add dp[2] + 1 as i fill the the cell i am currently at.
Similaly doing this for all 0’s i get my answer.
this logic worked for every test case i tried but gave wrong answer for testcase 2,4 and 5 dont realy know why.
Please provide corner test case and reason why this does not work.
Thank you.
Code Link: https://ide.codingblocks.com/s/103753