Pardonnez-moi pour écrire dans les codes:

for(int y = 0; y < rows; y++){

  for(int x = 0; x < columns; x++){
     // (x, y) would be the current space

     if(checkEmptySpace(x,y)){
       // empty space found

     }

  }

}

1. Démarrer
2. set Row = 0, colonne = 0
3. Si c'est l'espace libre:
   1. Obtenez le plus grand rectangle libre, commençant horizontalement
   2. sinon, et à la dernière colonne, et pas à la fin, rangée + 1, colonne = 0 et goto 3
   3. sinon sinon sur la dernière colonne, colonne + 1 et goto 3
   4. ailleurs finalement

      (Notez que 3.1 est le même algorithme, uniquement avec inversé libre / bloqué inversé et avec des coordonnées différentes)

Dans votre exemple, il apparaît que vous ne demandez pas d'exclure le chevauchement (par exemple 1 et 2 avoir le segment supérieur à gauche), donc peut-être que cela conviendra à vos besoins:

1. Divisez l'espace en rectangles en fonction des coins identifiés par les espaces occupés.

2. formez les "rectangles de base" en extensionnant les segments de ligne de ces coins aux bords de l'espace entier.

3. Utilisation de tout ordre systématique (par exemple de haut en bas, de gauche à droite):

   3.1. Sélectionnez un rectangle de base et étendez-le autant que possible avec d'autres rectangles de base qui ont un côté en commun.

   3.2. Former l'ensemble de tous (uniques) de tels rectangles étendus.

   Notez que cette recherche / repose sur les «rectangles de base» à partir de l'étape 2 et non sur le point point sur tout l'espace. La performance devrait donc être bien meilleure.

Vous recherchez quelque chose de similaire à Golf: eau courante

public class Program
{
    public static char occuppied;
    public static char vacant;
    public static char mark;
    public static void main(String[] args)
    {
        int rows = 7;
        int cols = 11;
        mark = 'A';
        occuppied = '#';
        vacant = '-';
        char[][] matrix = new char[rows][cols];
        setRect(matrix, vacant, 0, 0, rows, cols);
        setRect(matrix, occuppied, 3, 3, 2, 2);
        setRect(matrix, occuppied, 5, 5, 2, 6);

        print(matrix);
        for(int i = 0; i < rows; i++)
        {
            int colstart = 0;
            while((colstart = nextEmptyCol(matrix[i], colstart)) != -1)
            {
                int width = 0;
                for(int j = colstart; j < cols; j++)
                {
                    if(matrix[i][j] == vacant)
                        width++;
                    else
                        break;
                }
                if(width == 0)
                    continue;
                int height = 1;
                outer:
                for(; height + i < rows; height++)
                    for(int n = 0; n < width; n++)
                    {
                        if(matrix[i + height][colstart + n] == occuppied)
                            break outer;
                    }
                System.out.println("width = " + width + ", height = " + height);
                setRect(matrix, mark, i, colstart, height, width);
                print(matrix);
                mark++;
            }
        }
    }
    public static void setRect(char[][] matrix, char c, int startrow, int startcol, int numrows, int numcols)
    {
        for(int i = 0; i < numrows; i++)
            for(int j = 0; j < numcols; j++)
                matrix[startrow + i][startcol + j] = c;
    }
    public static void print(char[][] matrix)
    {
        int rows = matrix.length;
        int cols = matrix[0].length;
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
                System.out.print(matrix[i][j] + " ");
            System.out.println();
        }
        for(int i = 0; i < cols; i++)
            System.out.print("==");
        System.out.println();
    }
    public static int nextEmptyCol(char[] row, int start)
    {
        for(int i = start; i < row.length; i++)
            if(row[i] == vacant)
                return i;
        return -1;
    }
}

Je pense que vous pouvez implémenter un APPROCHE MONTECARLO .

Cordialement.

Je pense que considérer que juste des conrères n'obtiendront pas les meilleurs mathématiques.

Par exemple, dans l'image ci-dessous, la section "R" est la meilleure correspondance, mais ne commence dans aucun coin. < Pré> xxx

Voici l'algorithme que j'ai utilisé pour exactement le même cas:

Cela retournera une liste des rectangles d'espace vide .

1. commandez des obstacles connus dans une liste de haut à gauche au bas à droite
2. Créez un premier rectangle d'espace vide qui prend toute la zone que vous souhaitez vérifier
3. pour chaque obstacle (O) dans l'ordre:
   1. pour chaque espace vide qui chevauche O
      1. Supprimer le rectangle d'espace vide (ESR)
      2. Si ESR.LEFT , créez un nouveau rectangle d'espace vide (NESR) avec nesr.right = o.left et ajoutez-le à la liste des ESR Les autres obstacles doivent vérifier les chevauchements.
      3. Si ESR.Right> O.Right , créez de nouveaux ESR, NESR.LEFT = O.Right
      4. Si ESR.Bottom , crée de nouveaux ESR, nesr.top = o.bottom
      5. Si ESR.TOP> O.Top , crée de nouveaux ESR, nesr.bottom = o.top

         n.b: ceci est une séquence de si, pas d'autre si. Ce qui signifie que vous créez jusqu'à 4 nouveaux ESR pour chaque chevauchement.

         Explication :

         • Nous créons un seul "rectangle vide vide", puis nous vérifions chaque obstacle connu de savoir si elle se chevauche (elle le fait évidemment, car ce rectangle couvre tout ).
         • Le premier obstacle divisera le premier rectangle d'espace vide en jusqu'à 4 rectangles plus petits. Serré pour ne pas le chevaucher.
         • Le 2e obstacle vérifiera alors s'il chevauche l'un des rectangles d'espace vide nouvellement créés. Chaque rectangle qu'il chevauche est divisé plus loin, en jusqu'à 4 nouveaux rectangles. Aucun de ceux-ci ne chevauchera l'obstacle 1 ou l'obstacle 2.
         • Nous continuons d'aller comme ça jusqu'à ce que chaque obstacle ait été vérifié.
         • Nous nous retrouvons avec une liste d'espaces vides qui ne chevauchent pas d'obstacles. Nous aurons certainement des chevauchements cependant.