Java - 检查矩形 "fits" 是否为二维数组(2d 装箱)
Java - Check if a rectangle "fits" into a 2 dimensional array (2d bin packing)
所以基本上我想创建一个方法,将二维数组作为 1 个参数,将矩形的宽度和高度作为其他 2 个参数。二维数组仅包含二进制数(0 - 空单元格,1 - 已取单元格)。如果容器中仍有足够的空间容纳矩形,则该方法应该 return 为真。
我的主要问题是我不知道如何遍历二维数组,同时检查数组中是否确实存在大小为空 space 的 rectHeight*rectWidth。
现在我只检查 4 个顶点是否可用,但这显然不够。
for (int j = y; j < y + rowHeight - rectHeight + 1; j++){
for (int k = 0; k < bin[j].length - rectWidth + 1; k++){
if (bin[j][k] == 0 && bin[j][k + rectWidth - 1] == 0 && bin[j + rectHeight - 1][k] == 0 && bin[j + rectHeight - 1][k + rectWidth - 1] == 0){
isOne = true;
for (int l = j; l < j + rectHeight; l++){
for (int m = k; m < k + rectWidth; m++){
bin[l][m] = not_positioned.get(i).getId();
}
}
not_positioned.remove(i);
}
}
}
您可以使用覆盖图,其中空单元格是顶点:
在两个循环中实现会更容易(每个循环在一个单独的方法中):
//test data
private static int[][] bin = {
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
};
public static void main(String[] args) {
System.out.println(isEnoughtSpace(1, 1));// output - true
System.out.println(isEnoughtSpace(2, 2));// output - true
System.out.println(isEnoughtSpace(3, 3));// output - true
System.out.println(isEnoughtSpace(1, 3));// output - true
System.out.println(isEnoughtSpace(3, 1));// output - true
System.out.println(isEnoughtSpace(4, 1));// output - false
System.out.println(isEnoughtSpace(4, 5));// output - false
System.out.println(isEnoughtSpace(11,11));// output - false
System.out.println(isEnoughtSpace(0,0));// output - true
}
private static boolean isEnoughtSpace(int rectHeight, int recWidth) {
for(int row = 0; row <= (bin.length - rectHeight); row++) {
for(int col = 0; col <= (bin[0].length - recWidth); col++) {
if(isEnoughtSpace(row, col, rectHeight, recWidth)) {
return true;
}
}
}
return false;
}
private static boolean isEnoughtSpace(int rowIndex, int colIndex,int rectHeight, int recWidth) {
for(int row = rowIndex; row < (rowIndex+rectHeight) ; row ++) {
for(int col = colIndex; col < (colIndex+recWidth) ; col++) {
if(bin[row][col] == 1 ) {
return false;
}
}
}
return true;
}
您可能想要添加一些有效性检查(例如正宽度和高度)。
所以基本上我想创建一个方法,将二维数组作为 1 个参数,将矩形的宽度和高度作为其他 2 个参数。二维数组仅包含二进制数(0 - 空单元格,1 - 已取单元格)。如果容器中仍有足够的空间容纳矩形,则该方法应该 return 为真。
我的主要问题是我不知道如何遍历二维数组,同时检查数组中是否确实存在大小为空 space 的 rectHeight*rectWidth。
现在我只检查 4 个顶点是否可用,但这显然不够。
for (int j = y; j < y + rowHeight - rectHeight + 1; j++){
for (int k = 0; k < bin[j].length - rectWidth + 1; k++){
if (bin[j][k] == 0 && bin[j][k + rectWidth - 1] == 0 && bin[j + rectHeight - 1][k] == 0 && bin[j + rectHeight - 1][k + rectWidth - 1] == 0){
isOne = true;
for (int l = j; l < j + rectHeight; l++){
for (int m = k; m < k + rectWidth; m++){
bin[l][m] = not_positioned.get(i).getId();
}
}
not_positioned.remove(i);
}
}
}
您可以使用覆盖图,其中空单元格是顶点:
在两个循环中实现会更容易(每个循环在一个单独的方法中):
//test data
private static int[][] bin = {
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,0,0,0,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1},
};
public static void main(String[] args) {
System.out.println(isEnoughtSpace(1, 1));// output - true
System.out.println(isEnoughtSpace(2, 2));// output - true
System.out.println(isEnoughtSpace(3, 3));// output - true
System.out.println(isEnoughtSpace(1, 3));// output - true
System.out.println(isEnoughtSpace(3, 1));// output - true
System.out.println(isEnoughtSpace(4, 1));// output - false
System.out.println(isEnoughtSpace(4, 5));// output - false
System.out.println(isEnoughtSpace(11,11));// output - false
System.out.println(isEnoughtSpace(0,0));// output - true
}
private static boolean isEnoughtSpace(int rectHeight, int recWidth) {
for(int row = 0; row <= (bin.length - rectHeight); row++) {
for(int col = 0; col <= (bin[0].length - recWidth); col++) {
if(isEnoughtSpace(row, col, rectHeight, recWidth)) {
return true;
}
}
}
return false;
}
private static boolean isEnoughtSpace(int rowIndex, int colIndex,int rectHeight, int recWidth) {
for(int row = rowIndex; row < (rowIndex+rectHeight) ; row ++) {
for(int col = colIndex; col < (colIndex+recWidth) ; col++) {
if(bin[row][col] == 1 ) {
return false;
}
}
}
return true;
}
您可能想要添加一些有效性检查(例如正宽度和高度)。