Code not working

#1

https://practice.geeksforgeeks.org/problems/flood-fill-algorithm1856/1/?category[]=Matrix&category[]=Matrix&problemStatus=unsolved&page=2&query=category[]MatrixproblemStatusunsolvedpage2category[]Matrix#

#2

I tried to make it work, it passes the compilation case. It shows segmentation error in submission

#3

code seems correct , tell me the test case you are failing as i don’t have gfg account so can’t check.

#4

Bro I don’t now which test case is it failing for, it simply shows segmentation fault when I submit the code

#5

Is works fine for the basic test case they gave for compilation of the code

#6

Check now -.

#7

Please explain the change in brief

#8

It’s told in the question that To perform a “flood fill” , consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on.
You haven’t applied that condition rest remains same.

#9

I tried to understand it, But I am not able to. Please elaborate.
Also the change that you made: image[x][y]!=new_color, why did we add this?

#10

it means that if x and yth index of image is not equal to new color that we have to paint, then we will paint it. But if it’s already painted then we won’t paint it again. This is simple dfs check, the same you have done earlier to not visit, visited index.

#11

Let’s observe this if statement. It has two parts, if(image[x][y]==boundryColor && image[x][y]!=newColor.
Now adding this second check is confusing me (although you gave me the reason now but I am still not able to absorb it). For the if statement to be true both must be true. Now let’s say the first part is true, then the second part will always be true. if image[x][y] is already equal to boundrycolor how can it be ever equal to newColor. Please tell me the case which demonstrates the use of the addition.

(I know you are right, I removed the second if and the code showed segmentation error, it’s just that I am having difficulty in understanding)

#12

take this test case:

4 5
2 1 2 1 3
2 3 3 3 2
2 3 1 3 2
1 2 3 2 2
0 0 1

Its Correct output is:

1 1 2 1 3
1 3 3 3 2
1 3 1 3 2
1 2 3 2 2

Dry run this test case using above code, you will get the intuition for sure.

#13

I did. Still not getting it.
boundry_color = 2 for all calls.

At (0,0) the change occurs and out of 4 recursive calls, the above and left call return because of being outside the matrix. The right call returns because the value was 1 and not 2.
The only feasible call was for the below case (i.e 1,0).

Now at (1,0), four calls occur. Out, of for calls, left call returns because of being outside, right call returns because at (1,1) 3 is present. When above call happens i.e to (0,0) , it returns because at (0,0) now 1 is present because we had changed it just before so, if(image[x ][y]==boundry_color fails. For the down call, i.e. for call to (2,0), the change occurs and then again,

At (2,0), 4 calls are made. The left call returns because of being outside the matrix, the right call returns because 3 is present at (2,1). The down call return because (image[x ][y]==boundry_color fails as 1 is present at (3,0). For the above call, i.e. call to (1,0) , the call returns as we had changed it to 1 and image[x ][y]==boundry_color fails.

#14

Please point out What did I miss?

#15

This is what second if statement does see your 0 0 is 1 when you do up call, it’s already your new color right? so you won’t make a call again for this co-ordinate.
Check this

IMG_772C90E827D7-1
IMG_772C90E827D7-11808×647 402 KB

#16

when call happens from (1,0) to (0,0), if(image[x][y]==boundry_color) i.e. the first condition fails, only this much should suffice, no? As boundry_color =2 throughout.

#17

it will only be sufficient if we have already visited that array. but see when from 1,0 we are doing call for 2,0 we also need to check if 2,0 is equal to newcolor or not. If it is then it means no need to paint it, but if it’s not then we have to paint it with newColor.
In naive words the if condition means that all those indexes which we haven’t visited(image[x][y] != newColor) and our equal to boundary value 2(image[x][y] == boundary_color) we will colour them with color 1.

#18

So considering the call from (1,0) to (2,0) if the first condition can be true or false. If it is false, there’s no nee to further pursue it, if it is true, then it means that image[x][y]==boundry_color. And it can not ever be equal to new_color. So, we see the first condition seems to be sufficient.

it’s just like: if(a==1 and a!=2) if a is 1 there’s no need to check it for something else

#19

please check your inbox

#20

this will be right for 0,0 but what about 2,0 for that you have to check no?