Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

HW6 recovery algorithm

z
zaur (740 points)
3 6 8
in HW6 by (740 points)
edited by

I couldn't think of good algorithm for finding how to fit spesific matrix(spaceship) in another matrix.

something like fitting this

  **
  **
**++**
**++**
**++**
  **
  **     (spaceship)

in this

.

Algorithm that I wrote considers the spaceship as rectangle, but I think it's not the right solution, as there can be cases which will fit the figure without corners. Any ideas?

235 views

1 Answer

angelo.spognardi (8170 points)
75 155 224
by (8.2k points)
The idea of considering rectangles is a good starting point if you imagine the spaceship as a rectangle of one of the two dimensions + 2*hatches. Clearly, you should also perform an additional check for the hatches of the not-considered dimension. An exhaustive search for all the spaceships/points of the city is, also, an obvious (and effective) approach.