2017-12-30 70 views
-4

私は黒、白または混合の四角で構成された長方形のチョコレートバーを持っています。バーは50×50の正方形ではありません。私は2人の間でバーを分割することになっています(1つはすべて白い四角形を取得し、もう1つは黒色のものを混在させ、混合したものは問題ありません)。私はこのような亀裂の量が最も少ない方法を見つけるはずです。黒と白のチョコレートを分割するアルゴリズムが最も少なく、

Iは、この入力を与えられている:限りNの数であるM行(0 2が混合され、1は黒色手段、白を意味する) 次いで

MN(行数、列数) と

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

を合計7回割ることで分割することができます。

と、この1は、少なくとも24の亀裂を必要とします:

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 

私は2つの新しく作られたチョコレートバー片を分割するために必要な将来の亀裂の和の合計ように2枚のバー割れのようなものを考えていました可能なすべてのクラック(可能なクラックの高さ-1 +幅-1)からできるだけ少ないです。

この問題を解決するためのアルゴリズムについてのアドバイスはありますか、ありがとうございます。

編集:これを解決するコードを書くために、私はzenwraightのおかげで管理しましたが、別の問題が発生しました。これは実際には効率が悪く、開始チョコレートバーが30x30よりも大きくなると実際には使用できません。 (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); 
} 

私は、この入力を解決することを目指しています:2秒の下で

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 

、はるかに私の現在のプログラムよりも速い時間であります。このクラックの最小量は126です。

+0

申し訳ありませんが、何が間違っているのか分かりません。なぜ私は非常に多くのdownvotesを得ていますか?私は質問が十分にはっきりしていると思いますか? –

+1

http://idownvotedbecau.se/noattempt/ –

+1

次の質問を投稿する前に[ツアー](https://stackoverflow.com/tour)に行き、[ヘルプセクション](http:// [どのような種類の質問を避けるべきですか?](http://stackoverflow.com/help/on-topic)を読んでください。あなたの質問がルールに合っていると確信しているなら、[よくある質問と答え](http://stackoverflow.com/help/how-to-ask)トピック上の質問。 –

答えて

1

良い質問ですが、私は上記の問題に取り組むために再帰を利用するアプローチを念頭に置いています。

各レベルまたはステップでは、バーを水平または垂直に分割する2つのオプションがあります。

例をあげてアルゴリズムを理解してみましょう。

例: -

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

になり、我々は破るのであれば最初のステップで私たちの matleft

0 
1 
1 
2 

matrightになり、水平方向であるのは、私達の機能minBreaks(int n, int m, int matleft, int right)

を呼びましょう

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

今、私たちは縦これを壊れていた場合も同様たちのmatleft

0 1 1 1 

matrightになりますが

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

今、あなたは、次の再帰呼び出し

にこのmatleftmatrightに沿って通過され、行のサイズが1またはcol = 1の各呼び出しで、同じ値の接続されたコンポーネントをチェックして、 maxleftの垂直場合の例と同様に接続されているコンポーネント

のカウント - >0 1 1 1、あなたはすべてのケースのために同様に2

を返し、メソッドの端部が

min between break horizontally and vertically

を返します。

希望します。

+0

はい、助けてくれました。私は実際には同じことを考えていました。しかし、私があなたの考えを正しく理解しているならば、最初の行(水平)または列(垂直)の直後に行列を壊すだけですが、それは行列をどこでも破ることができるということです。また、列または行のサイズが1の場合にのみ行列を分割できないかどうかを確認していますか?しかし、2x2行列を1または0だけで除算するとどうなるでしょうか? –

+0

とにかく、もう一度確認したい場合は、質問を更新しました。 :) –

関連する問題