Algorithmus zum Teilen von schwarzen und weißen Schokoriegel mit der geringsten Anzahl von Brüchen

Question

Ich habe einen rechteckigen Schokoriegel, der aus Quadraten entweder schwarz, weiß oder gemischt besteht. Die Bar ist nicht größer als 50x50 Quadrate. Ich soll den Balken zwischen zwei Leuten aufteilen (einer bekommt alle weißen Quadrate und einer den schwarzen, gemischte spielt keine Rolle), indem man ihn entweder horizontal oder vertikal knackt. Ich sollte eine Methode mit der geringsten Anzahl solcher Risse finden.

I gegeben werde diese Eingabe:

MN (Anzahl von Zeilen, Anzahl von Spalten) und dann M Reihen, die N Zahlen sind lang (0 bedeutet weiß, 1 bedeutet, schwarz, 2 gemischt ist) so zum Beispiel bar wie folgt beschrieben:

4 4 
0 1 1 1 
1 0 1 0 
1 0 1 0 
2 0 0 0 

kann geteilt werden, indem man es insgesamt sieben Mal knackt.

und dieser muss mindestens 24 Risse:

5 8 
0 1 0 1 0 1 0 2 
1 0 2 0 2 0 1 0 
0 2 0 2 0 1 0 2 
1 0 2 0 2 0 1 0 
0 1 0 1 0 1 0 2 

Ich dachte an so etwas wie die Bar in zwei Stücke Cracken so dass die Summe der Beträge der zukünftigen Risse benötigt zwei neu gemacht Schokoriegel Stücke zu teilen ist das Geringste möglich von allen möglichen Rissen (welche Höhe -1 + Breite -1 des gegenwärtigen Stabstückes wird geknackt)

Ich würde jeden Rat auf einem Algorithmus schätzen, dieses Problem zu lösen, danke.

EDIT: Ich habe geschafft, auch dank zenwraight, einen Code zu schreiben, der das löst, aber ich stieß auf ein anderes Problem, es ist wirklich ineffizient und wenn der Startschokoriegel größer als 30x30 wird, ist es praktisch unbrauchbar. sowieso der Quellcode (geschrieben in C):

#include <stdio.h> 
#include <stdlib.h> 

const int M, N; 
int ****pieces; 
int r = 0; 
int ri = 0; 
int inf; 

void printmatrix(int **mat, int starti, int startj, int maxi, int maxj) { 
    for (int i = starti; i < maxi; i++) { 
     for (int j = startj; j < maxj; j++) { 
      printf("%d ", mat[i][j]); 
     } 
     printf("\n"); 
    } 
} 

int minbreaks(int **mat, int starti, int startj, int maxi, int maxj, int depth) { 
    if (pieces[starti][startj][maxi][maxj] != 0) { 
     r++; 
     return pieces[starti][startj][maxi][maxj]; 
    } else { 
     ri++; 
     int vbreaks[maxj - 1]; 
     int hbreaks[maxi - 1]; 
     for (int i = 0; i < maxj; i++) { 
      vbreaks[i] = inf; 
     } 
     for (int i = 0; i < maxi; i++) { 
      hbreaks[i] = inf; 
     } 
     int currentmin = inf; 
     for (int i = starti; i < maxi; i++) { 
      for (int j = startj; j < maxj - 1; j++) {//traverse trough whole matrix 
       if (mat[i][j] != 2) { 
        for (int k = startj + 1; k < maxj; k++) {//traverse all columns 
         if (vbreaks[k - 1] == inf) {//traverse whole column 
          for (int z = starti; z < maxi; z++) { 
           if (mat[z][k] != 2 && mat[i][j] != mat[z][k]) { 
            /* printmatrix(mat, starti, startj, maxi, maxj); 
            printf("brokenv in depth:%d->\n", depth); 
            printmatrix(mat, starti, startj, maxi, k); 
            printf("and\n"); 
            printmatrix(mat, starti, k, maxi, maxj); 
            printf("****\n");*/ 
            vbreaks[k - 1] = minbreaks(mat, starti, startj, maxi, k, depth + 1) + minbreaks(mat, starti, k, maxi, maxj, depth + 1); 
            if (vbreaks[k - 1] < currentmin) { 
             currentmin = vbreaks[k - 1]; 
            } 
            break; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     for (int i = starti; i < maxi - 1; i++) { 
      for (int j = startj; j < maxj; j++) { 
       if (mat[i][j] != 2) { 
        for (int k = starti + 1; k < maxi; k++) { 
         if (hbreaks[k - 1] == inf) { 
          for (int z = startj; z < maxj; z++) { 
           if (mat[k][z] != 2 && mat[i][j] != mat[k][z]) { 
            /* printmatrix(mat, starti, startj, maxi, maxj); 
            printf("brokenh in depth:%d->\n", depth); 
            printmatrix(mat, starti, startj, k, maxj); 
            printf("and\n"); 
            printmatrix(mat, k, startj, maxi, maxj); 
            printf("****\n");*/ 
            hbreaks[k - 1] = minbreaks(mat, starti, startj, k, maxj, depth + 1) + minbreaks(mat, k, startj, maxi, maxj, depth + 1); 
            if (hbreaks[k - 1] < currentmin) { 
             currentmin = hbreaks[k - 1]; 
            } 
            break; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     if (currentmin == inf) { 
      currentmin = 1; 
     } 
     pieces[starti][startj][maxi][maxj] = currentmin; 
     return currentmin; 
    } 
} 

void alloc(int i, int j) { 
    pieces[i][j] = malloc(sizeof (int*)*(M + 1)); 
    for (int y = i; y < M + 1; y++) { 
     pieces[i][j][y] = malloc(sizeof (int)*(N + 1)); 
     for (int x = j; x < N + 1; x++) { 
      pieces[i][j][y][x] = 0; 
     } 
    } 
} 

int main(void) { 
    FILE *file = fopen("pub08.in", "r"); 
    //FILE *file = stdin; 
    fscanf(file, "%d %d", &M, &N); 
    int **mat = malloc(sizeof (int*)*M); 
    pieces = malloc(sizeof (int***)*M); 
    for (int i = 0; i < M; i++) { 
     mat[i] = malloc(sizeof (int)*N); 
     pieces[i] = malloc(sizeof (int**)*N); 
     for (int j = 0; j < N; j++) { 
      int x; 
      fscanf(file, "%d", &x); 
      mat[i][j] = x; 
      alloc(i, j); 
     } 
    } 
    inf = M * (M + 1) * N * (N + 1)/4 + 1; 
    int result = minbreaks(mat, 0, 0, M, N, 0); 
    printf("%d\n", result); 
    printf("ri:%d,r:%d\n", ri, r); 
    return (EXIT_SUCCESS); 
} 

Ich bin mit dem Ziel diesen Eingang zu lösen:

40 40 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 2 1 2 1 2 0 0 1 2 2 0 0 0 0 0 0 0 0 1 1 2 1 2 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 2 2 0 1 1 1 1 1 0 0 1 2 2 0 0 0 0 0 1 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 2 2 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 1 1 2 2 0 0 0 1 2 2 1 2 1 0 0 0 0 0 1 2 1 2 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 2 2 1 2 0 0 0 0 0 2 1 2 2 0 0 0 0 0 2 1 2 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 2 2 2 1 1 0 0 0 0 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 
0 2 1 2 1 0 2 2 2 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 0 2 2 1 0 0 0 0 0 0 
0 2 2 1 2 0 1 2 2 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 
0 2 2 1 2 0 0 0 0 2 1 2 1 2 1 1 2 0 2 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 2 2 2 2 1 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 2 1 1 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 0 0 0 0 
0 0 0 0 0 0 0 2 1 2 0 0 2 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 1 0 0 0 0 
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0 
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 2 0 1 1 1 2 1 2 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 2 1 2 2 2 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 1 2 1 1 2 2 0 0 0 0 0 
0 0 0 0 0 0 1 2 1 2 2 1 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 2 1 2 0 0 0 0 0 
0 0 0 0 0 0 1 2 2 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0 
0 0 0 0 0 0 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 
0 0 0 0 0 0 1 2 2 2 1 1 1 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 2 2 2 1 0 
0 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 1 1 1 2 2 0 0 0 0 0 0 0 0 0 1 2 1 1 0 
0 0 0 2 1 1 2 2 0 1 2 1 1 0 0 0 0 0 2 2 1 2 2 1 2 2 0 0 0 0 0 0 0 0 0 1 2 2 2 0 
0 0 0 2 2 2 1 1 0 0 1 2 2 2 0 0 0 0 2 2 2 1 1 2 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 2 1 2 2 1 1 0 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 2 2 2 2 1 0 1 1 1 1 1 1 2 1 1 2 2 1 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 1 0 0 2 1 1 1 2 1 2 0 0 1 2 1 2 1 2 2 0 0 0 0 0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 1 2 2 1 1 2 2 1 1 1 1 1 1 1 2 1 0 0 0 0 0 0 0 2 2 2 0 0 0 
0 0 0 0 0 0 0 1 1 1 2 0 0 1 1 1 2 2 1 2 2 2 1 0 0 0 1 1 1 0 0 0 0 0 1 2 1 0 0 0 
0 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 2 1 1 1 2 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 2 0 2 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0 
0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0 
0 0 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

in weniger als 2 Sekunden, was als die von meinem aktuellen Programm viel viel schnelle Zeit ist . die minimale Menge an Rissen für dieses ist 126.

Answer 1

Schöne Frage, ich habe einen Ansatz im Auge, der Rekursion verwendet, um das obige Problem anzugehen.

So wie auf jeder Ebene oder Schritt haben Sie zwei Möglichkeiten, den Balken horizontal oder vertikal zu teilen.

Also lasst uns den Algorithmus mit einem Beispiel verstehen.

Beispiel: -

4 4 
0 1 1 1 
1 0 1 0 
1 0 1 0 
2 0 0 0 

Jetzt nennen wir unsere Funktion minBreaks(int n, int m, int matleft, int right)

So auf den ersten Schritt, wenn wir brechen horizontal ist unser matleft

wird

0 
1 
1 
2 

und matright

wird

1 1 1 
0 1 0 
0 1 0 
0 0 0 

nun in ähnlicher Weise, wenn wir diese vertikal gebrochen hatte unsere matleft

0 1 1 1 

sein und matright wird

1 0 1 0 
1 0 1 0 
2 0 0 0 

Jetzt sein passieren Sie entlang dieser matleft und matright in der nächsten Rekursion Anruf

Und dann bei jedem Aufruf, wenn die Größe der Zeile = 1 oder col = 1 ist, können Sie die verbundenen Komponenten mit dem gleichen Wert überprüfen und den Wert zurückgeben zählen der angeschlossenen Komponenten

Wie zum Beispiel für vertikal Fall von maxleft ->0 1 1 1, werden Sie 2.

zurückkehren Ebenso für alle Fälle und den Endteil des Verfahrens kehrt

min between break horizontally and vertically

Hoffe, das hilft!