[Community Puzzle] Flood fill Example

https://www.codingame.com/training/medium/flood-fill-example

Send your feedback or ask for help here!

I find the rules quite unclear on two points:

  1. Is is really not clear that apparition of + sign doesn’t stop the flood fills (in other word, +'s propagate as well)
  2. It is really not clear that meetings between towers with the same ID result in a + sign
2 Likes

Your 1. is very clear, there’s no mention of floodfill at all except in the tag. It’s all about “closest tower”, so it can be defined for any spot.

I agree with your 2., it’s not very clear and you discover it only with test 5. I’ll try to edit to make it clearer.

2 Likes

I don’t understand why at time = 2 there is not a + in (2,1) , since b and b arrive at the same time. (same (4,1) and (2,3)). Thanks

Which case?

In example :

Consider the following grid:

...#.
A#...
#..B.
.....

At time = 1, they will reach…

A..#.
A#.B.
#.BBB
...B.

At time = 2, they will reach…

AA.#.
A#BBB
#BBBB
..BBB

if you are :
.B
BB

why
BB
BB

and not
+B
BB
?

Because B is only one tower; the purpose of the flood fill here is to mark the coverage of that tower, it is not to grow more towers. Compare with test case 5, where there are two towers A.

Sorry but I do not understand. I saw case n°5, but I don’t see the difference.

The rule stated by the statement is that “If 2 towers can reach a spot at the exact same time, mark that spot ‘+’, even if both towers share the same I.D…”

Tower B is just one tower, so it does not fall within the scope of the above rule.

But in test case 5, there are two towers both named A. “Two towers sharing the same I.D. of A” fall within the scope of the above rule.

In short, you count the number of letters in the input data (the initial state), and that is the number of towers you have to deal with.

And if you are still confused, remember that you are converting a map of towers into a map of tower coverage. The flood fill does not indicate additional towers (there are NOT tens of towers of the same I.D. on the map!); the I.D.s on the map you have to output merely show which tower covers each spot.

ok, thanks, i’m starting to understand the problem. I can’t see how to solve it yet but I’ll think about it and come back if I can’t.

1 Like

I got it ! Thank you for all your advice.