HW6 recovery algorithm

Question

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?

Answer 1

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.