# [Community puzzle] Zergling rush

This topic is about the puzzle Zergling rush.

I am stuck with the impassable obstacles as I kind of thinking there must be a simpler way other than checking the relation between each obstacles one by one. Any ideas or advice would be appreciated.

Think like Zergling, from each cell on the sides of the map (top, bottom, left, right) try to fill all the map, and if you touch a building (even diagonally) put a â€śzâ€ť there.

1 Like

You can use the algorithm of Disjoint-set. (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

It easy to program and have low cost of execution.

You could also reverse it. For all locations adjacent to a building, see if thereâ€™s a path outside. I guess the flood-fill is more efficient.

Are you saying that the correct solution for map:
.#.
#B#
.#.

will be
z#z
#B#
z#z
Doesnâ€™t this contradict the statement that zerglings will surround only the buildings that they can reach? To me it looks like the building canâ€™t be reached so no zerglings should be displayed.

Note that Iâ€™m currently unable to pass validator 3 on submission so just trying to understand what exactly did I miss.

From the statement:

Zerglings will surround all enemy buildings they can reach, taking up horizontally, vertically, and diagonally adjacent cells

So yes, Zerglings will stick to buildings even diagonally

My confusion here is that the building canâ€™t actually be reached since zerglings canâ€™t move diagonally - they can only surround diagonally as long as there is a horizontal or vertical path to the building.

Anyway, even with this adjustment I still canâ€™t pass the validator

Move on X-Y axis, â€ścaptureâ€ť on X-Y AND diagonal.
I solved it this way, a pathfinder that moves on X-Y but captures also on diagonal.

I used the exact same strategy but moved from buildings towards borders. Now I changed to move from borders and all validators passed. Itâ€™s a pity the validator test cases arenâ€™t available even after the puzzle is 100% solved, because Iâ€™m too curious to find what my bug was

Thanks for the hint

Hi, I think thereâ€™s a bug with the Lua validator. I canâ€™t pass any validators or testcases even tough my output seems right.
For instance, I got with the first test case
Standard Output Stream:
â€¦
.zzz.
.zBz.
.zzz.
â€¦

``````Failure
Found:    Nothing
Expected: Nothing
``````

But if I take this exact same testcase into custom it pass.

@Manzazuu: You might have an extra new line at the end of the output. That was the issue in my case on another puzzle.