How should I fit a shape into a space?

Question

Suppose I have the following shape (String type);

..ee
e..e

And the following space:

||..
.|..

My method shapeFitsAt() determines if the given shape may be placed at the indicated row/col position. The row,col indicates where the upper left corner [block (0,0)] of the shape would be placed. A shape would not fit if one of its filled blocks would conflict with an existing filled block in the space or would be out of bounds in the space. "|" means block/obstacle while "." means an empty space. So if I place the above shape into the space, it would look like this:

||ee
e|.e

Please can smb help how to approach fitting a shape into a space? Thanks in advance!

public class CreateSpace {

    private int height;
    private int width;
    private char[][] space = new char[height][width];
    private Shape originalShape;

    public CreateSpace(int height, int width, char[][] space, Shape shape)
    {
        this.height = height;
        this.width = width;
        this.space = space;
        this.originalShape = shape;
    }
public boolean shapeFitsAt(int row, int col, Shape shape)
    {

        if(row < 0 || row >= height || col < 0 || col >= width)
            throw new FitItException("Oops! Out of bounds in CreateSpace class! Go and check!");

        else if(space[row][col] == '|' || space[row][col] == this.originalShape.getDisplayChar())
            throw new FitItException("The space position is already filled out with a wall or a character. GO CHECK CreateSpace class!");

        else
        {

        }

    }

Answer 1

A solution would be to "linearize" the patterns into 2 bitsets (one for the shape, one for the obstacles).

Put 1's where the symbols must be preserved in the shape bitset, and 0's averywhere else ; put 0's where the obstacles are, and 1's elsewhere in the "obstacle" bitset.

Ex:

..ee    -->    ..eee..e    -->    00111001
e..e

||..    -->    ||...|..    -->    00111011
.|..

Then AND the two bitsets, and see if the result is the same as the shape bitset. If is if, the shapes fit ; if not, at least one obstable is in the way.

    Shape : 00111001
Obstacles : 00111011
      AND : 00111001  ==  Shape bitset => OK !

Quick and efficient, and you can re-use the obstacle bitset to test multiple shape patterns.