[Community puzzle] Unflood The World

When i started this one i thought it was “easy” and 10 mins later i had have a solution that made all tests green, but missed 3 validators. I looked into the posts here and figured out, that this on is rated as “very hard” ;), with missing testcases. So i designed a “new” test
5 5
1 1 1 1 1
1 4 4 4 1
1 4 2 4 1
1 4 4 4 1
1 1 1 1 1
with solution 2
after i passed that one, all validators also went green ;).

1 Like

I pass all testcases but miss validator Maze 2. Do you have some new testcase to help ?

Do these previous comments help you?

https://forum.codingame.com/t/community-puzzle-unflood-the-world/1941/16

https://forum.codingame.com/t/community-puzzle-unflood-the-world/1941/20

No, I have read all the comments.
This is my strategy:

  • list all numbers that don’t have lower neighbors (local minimum)
  • for each of these minima, perform a depth-first search to connect all cells of the same level and determine a set of distinct groups
  • eliminate false positives: for each group, recheck if these cells don’t have a lower neighbor and if so, eliminate the group
  • count the number of remaining group

Your strategy sounds correct :thinking: Maybe there’s a bug in the implementation?

If you want, you may send your code to me in private message and I’ll take a look.

1 Like

Thanks @5DN1L for your testcase, I could fix my error: when I created a new group I forgot to update the index of the element in the groups list.
This is the testcase that helped me if that can help you:

Input

5 5
6 1 5 4 2
1 4 4 4 1
4 6 1 1 8
6 1 6 8 9
1 1 2 2 5

Output

5
1 Like