问题描述
我有一个矩形的巧克力棒，它由黑色，白色或混合的正方形组成.条形不能大于50x50平方.我应该通过在水平方向或垂直方向上将其分开来在两个人之间划分界限(一个人获得所有白色方块，一个人获得黑色的方块，混合的无关紧要).我应该找到一种裂缝最少的方法.
I have a rectangular chocolate bar that consists of squares either black, white or mixed. The bar being not bigger than 50x50 squares. I'm supposed to divide the bar between two people(one gets all the white squares and one the black ones, mixed ones don't matter), by cracking it either horizontally or vertically. I'm supposed to find a method with the least amount of such cracks.
我得到了以下输入:
M N(行数，列数)然后M行的N个数字长(0表示白色，1表示黑色，2被混合)例如，酒吧描述如下:
M N (number of rows, number of columns)and then M rows that are N numbers long(0 means white, 1 means black, 2 is mixed)so for example bar described like this:
4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0
可以通过总共破解七次来划分.
can be divided by cracking it seven times in total.
这至少需要24条裂缝:
And this one needs at least 24 cracks:
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
我正在考虑将巧克力条分成两部分，这样，将所有新的巧克力条(将其分为-1高度和宽度)，将两块新制作的巧克力块分开所需要的未来裂纹总和是最小的当前条形的-1破裂)
I was thinking about something like cracking the bar in two pieces so that the sum of sums of future cracks needed to divide two newly made chocolate bar pieces is the least possible from all the possible cracks (which is height -1 + width -1 of the current bar piece being cracked)
感谢zenwraight，我设法编写了解决此问题的代码，但我遇到了另一个问题，这确实效率不高，如果起始巧克力块的尺寸大于30x30，则几乎无法使用.无论如何，源代码(用C编写):
I managed, also thanks to zenwraight, to write a code that solves this but I encountered another problem, it is really inefficient and if the starting chocolate bar gets bigger than 30x30 it's practically unusable.Anyway the source code (written 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);
}
我旨在解决此输入问题:
I am aiming to solve this input :
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
在2秒以内，这比我当前程序的时间要快得多.此裂纹的最小数量为126.
in under 2 seconds, which is much much faster time than that of my current program. The minimum amount of cracks for this one is 126.
推荐答案
很好的问题，我想到了一种利用递归来解决上述问题的方法.
Nice question, I have an approach in mind which makes use of recursion to tackle the above problem.
因此，在每个级别或步骤上，您都有两个选项可以水平或垂直拆分条形图.
So as at each level or step you have two options either to split the bar horizontally or vertically.
所以让我们通过一个例子来了解算法.
So let's understand the algorithm with an example.
示例:-
4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0
现在让我们调用函数minBreaks(int n, int m, int matleft, int right)
因此，第一步，如果我们在水平方向上折断，我们的matleft将是
So at first step if we break is horizontally our matleft will be
0
1
1
2
和matright将是
1 1 1
0 1 0
0 1 0
0 0 0
现在类似地，如果我们将其垂直打破，我们的matleft将是
Now similarly if we had broken this vertically our matleft will be
0 1 1 1
和matright将是
1 0 1 0
1 0 1 0
2 0 0 0
现在，您在下一个递归调用中传递此matleft和matright
Now you pass along this matleft and matright in next recursion call
然后在每次调用时，如果row = 1或col = 1，您可以检查相同值的连接组件并返回连接组件的计数
And then at each call when size of row = 1 or col = 1, you can check the connected components of same value and return the count of connected components
例如对于maxleft-> 0 1 1 1的垂直情况，您将返回2.
Like for example for vertically case of maxleft -> 0 1 1 1, you will return 2.
对于所有情况类似，该方法的结尾部分将返回
Similarly for all the cases and the end part of the method will return
min between break horizontally and vertically
希望这会有所帮助！
这篇关于中断次数最少的黑白巧克力条分割算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！