[Community Puzzle] Cloudy Weather

https://www.codingame.com/training/hard/cloudy-weather

Send your feedback or ask for help here!

Created by @Niako,validated by @JBM,@R2B2 and @Deltaspace.
If you have any issues, feel free to ping them.

please help me.I use A* findPath, However, it’is timeout…I can’t understand how to deal it

Hard to tell without more details, but the way I handled it was to replace the usual “step by 1” of pathfinding algorithms by “step by X” to cover long distances in one go and save performance.
This worked fine for me with Dijkstra, I assume it should also be the case with A*.

2 Likes

A first good idea was given by @Djoums above. And by the way, the puzzle was designed to be seamlessly solvable with Dijkstra (even though, considering the given maps, A* would probably be faster).

Here is a more detailed hint if it may help though (/!\ spoiler)

Consider a simple map as the one on the left below where the numbers (all 1 for now) indicate the heights of the lines and the widths of the columns.
As some consecutive lines/columns are identical, this map could be “compressed” into the smaller one on the right.

  1111111         232
1 .......       1 ...
1 ..███..   ->  2 .█.
1 ..███..       1 ...
1 .......
1 Like