HW6 recovery algorithm

zaur (740 points)
3 6 8
asked Jan 14 in HW6 by zaur (740 points)
edited Jan 14 by zaur

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?


1 Answer

angelo.spognardi (4680 points)
37 63 96
answered Jan 16 by angelo.spognardi (4,680 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.