Rules
Find the largest possible square on a map while avoiding obstacles.
Empty spaces are represented by a '.' and obstacles by a 'o'.
Map example :
Solved map example:
Methods
I tried two ways to find the square. Firstly, a simple method that was to look for the largest square at each point on the map. Secondly, i did some research on dynamic programming.
Simple method
The simple method was to look for the largest square at each point on the map. It was slow. So i tried to
optimize it by simple tricks :
- looking for the largest square at each point, but beginning with the largest fount for the moment.
- stop looking at coordinate that are closest to the edge of the map than the largest square found for the moment.
With this method, the program can solve a 10 000 * 10 000 map in 8 second, what is too long. So i was looking for a faster method.
Dynamic programming method
I did some research on dynamic programming and i found a strange method that use a 2nd array with integers. The goal was to look at each point on the map, and fill it with the minimum value around plus one :
So, the biggest value in the second array, where at the end of the biggest square :
So, there remain only to fill the map with 'x' from the biggest number's position.
With this method, the program can solve a 10 000 * 10 000 map in 2 second only !
Conclusion
The dynamic programming, by using unnatural method, is more efficient while it's more difficult to find.
Ha le projet BSQ, plein de bons souvenirs de tek1 :)