I'm trying to mark which component every cell is in but it is not wokring

#1

Please help me through the code, I’m for now trying to mark which component every cell is in and then I want to try to get the number of elements in each component. But after that I don’t know how to find where to add the grass.
Please help with the logic.
code-https://ide.codingblocks.com/s/342336

#2

@amanb25
Will get back to you ASAP.

#3

@amanb25
There was an error in your dfs code and the way you set the colors.
This is the updated code.

You were passing 0 as the color initially which lead to an infinite loop. I thus sent colors from 1.

Refer to this code and try out building the solution on this.

#4

okay thank you I’ll try building on this now

#5

code- https://ide.codingblocks.com/s/342951 The logic I’ve used is- 1) Make a component matrix which marks every component. 2) have a count array to check which component is how big. 3) finally i go through the matrix again and keep a variable c which stores the value of the current component (col), to check if the component is being repeated or not.

#6

@amanb25
You should try it this way. Now that you know which cell belongs to which component, go to every water cell and check if its adjacent cells can be combined by converting it to land. This can be done in constant time. Do it for every water cell.

Revert in case you face any difficulty.

#7

You should try it this way. Now that you know which cell belongs to which component, go to every water cell and check if its adjacent cells can be combined by converting it to land. This can be done in constant time. Do it for every water cell.

Revert in case you face any difficulty.

#8

I did that in my code and it gives the right answer for some of the test cases but not all.

#9

@amanb25
This is the updated code.

There were some errors.
Please set the size of the array to the constraints given in the question statement. The array was of smaller dimensions because of which there was an error.

Your approach was correct but there was a flaw in the implementation. Go through the code once and look at the last portion of the code. Revert in case you face any difficulty. I have stored the unique colors in the set so as to avoid adding the same components again.

If my explanation was able to resolve your doubts, please mark this doubt as resolved.

1 Like