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.