Алгоритм поиска Java для Matrix Fit для доступного пространства

Question

У меня есть космическая матрица, как

|....
..|..
.....
||...

, где . - это пустое пространство, а | - не пустое место.

и у меня есть 3 формы, как

TTT                 E.E                   ..L
                    ..E                   L.L
                    EEE

. также пусто. Теперь я хочу разместить эти фигуры в матрице пространства, используя код Java.

ожидаемое пространство выглядит как

|.ELE
.L|LE
..EEE
||TTT

может быть другая возможность подгонки

Код входного файла "problem1.txt"

SPACE
|.......
..|||..|
..|.|...
........

SHAPE T
TTTT

SHAPE e
..e
eee

SHAPE t
.t.
ttt

SHAPE r
rr
rr

SHAPE i
i..
iii

SHAPE s
.ss
ss.

Здесь мой код для чтения файла в массиве

File f = new File("problem1.txt");
      FileReader fr = new FileReader(f);
      int pos = 0;
      Scanner s = new Scanner(fr);


      // space class
      SpaceClass space = new SpaceClass();
      List<Shapeclass> shapeClasses = new ArrayList<Shapeclass>();
      Shapeclass shapeClass = null;

      boolean spaceStated = false;
      while(s.hasNext()) {
          //read trim line
          String line = s.nextLine().trim();
          if("".equals(line)){
              continue;
          }
          //CHECK For Space

       if("SPACE".equals(line.trim().toUpperCase())) {
           pos = -1;
           spaceStated=true;
           continue;
       }

       //check for space
       if(line.trim().toUpperCase().startsWith("SHAPE")) {
           pos = -1;
           spaceStated=false;
           shapeClass = new Shapeclass();
           shapeClasses.add(shapeClass);
           continue;
       }

       pos++;
       //adding for space
       if(spaceStated) {
           space.addRow(pos, line);
       }else{
           //adding for shape
           shapeClass.addRow(pos, line);
       }
      }

SpaceClass Похож на

public class SpaceClass{

    private int height=0;
    private int width=0;
    private char[][] s = new char[50][50]; 

    public SpaceClass() {}

    public void addRow(int rowNo, String row) throws Exception {
        if(this.width > 0 && this.width != row.length()) {
            throw new Exception("Invalid Input for SPACE at row : " + rowNo + " and row :- " + row);
        } else {
            char[] ch = row.toCharArray();
            for(int i=0,j=ch.length;i<j;i++) {
                s[rowNo][i] = ch[i];
            }
            this.width = ch.length;
            this.height += 1;
        }
    }

}

И ShapeClass выглядят как

public class Shapeclass{

    private int height;
    private int width;
    private char[][] s = new char[50][50];
    int rotate=0;

    public void addRow(int rowNo, String row) throws Exception {
        if(this.width > 0 && this.width != row.length()) {
            throw new Exception("Invalid Input for SPACE at row : " + rowNo + " and row :- " + row);
        } else {
            char[] ch = row.toCharArray();
            for(int i=0,j=ch.length;i<j;i++) {
                s[rowNo][i] = ch[i];
            }
            this.width = ch.length;
            this.height += 1;
        }
    }

}

Теперь я хочу новый класс Space с Fit all Shape