[EPITECH] BSQ project

in #epitech7 years ago

image.png

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 :
bsq_presentation_1.png

Solved map example:
image.png

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 :
image.png
So, the biggest value in the second array, where at the end of the biggest square :
image.png
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.

Sort:  

Ha le projet BSQ, plein de bons souvenirs de tek1 :)