私は黒、白または混合の四角で構成された長方形のチョコレートバーを持っています。バーは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です。
申し訳ありませんが、何が間違っているのか分かりません。なぜ私は非常に多くのdownvotesを得ていますか?私は質問が十分にはっきりしていると思いますか? –
http://idownvotedbecau.se/noattempt/ –
次の質問を投稿する前に[ツアー](https://stackoverflow.com/tour)に行き、[ヘルプセクション](http:// [どのような種類の質問を避けるべきですか?](http://stackoverflow.com/help/on-topic)を読んでください。あなたの質問がルールに合っていると確信しているなら、[よくある質問と答え](http://stackoverflow.com/help/how-to-ask)トピック上の質問。 –