我有一个项目，我必须从 3x1 和 4.5x1 的块创建一个面板。为了结构完整性，块之间的空间不得在相邻行中排列。我必须计算所有可能的组合。一些例子是 7.5x1 面板有 2 种可能的解决方案，7.5x2 面板有 2 种可能的解决方案，12x3 面板有 4 种可能的方式，27x5 有 7958 种可能的方式。我的问题是当我进入更高的宽度时，我得到的解决方案比我应该得到的更多。我认为这与我有可能得到重复的表有关，但我看不到它发生在哪里或如何修复它。任何帮助将不胜感激。代码如下。
import java.util.ArrayList;
import java.util.List;
import puzzle.Row;
public class panel {
/**
* This program will return the number of unique tables that for structural integrity don't have blocks that line up
* in adjacent rows. The width is to be between 3 and 48 and the height between 1 and 10. The width
* should also be a multiple of 0.5.
*
* @param width, height
* @return totalTables
*/
public static void main(String[] args) {
int width = 0;
int height = 0;
// Check to make sure that two arguments were passed.
if (args.length != 2) {
System.out.println("Please enter both a height and a width.");
System.exit(1);
} else {
// Check that a data type of double was entered.
if ( ( args[0].matches("^[0-9]+(\\.[0-9]+)?$") ) &&
( Double.valueOf(args[0].trim()).doubleValue() >= 3.0 ) &&
( Double.valueOf(args[0].trim()).doubleValue() <= 48.0 ) &&
( Double.valueOf(args[0].trim()).doubleValue()) % 0.5 == 0 ) {
width = (int) (Double.valueOf(args[0].trim()).doubleValue() * 2); // Double the width so that we are working with an integer.
} else {
System.out.println("Please enter a number for your width that is between 3 and 48 and divisable by 0.5.");
System.exit(1);
}
// Check that a data type of integer was entered.
if ( ( args[1].matches("^[0-9]+$") ) && ( Integer.valueOf(args[1]) >= 1 ) && ( Integer.valueOf(args[1]) <= 10 )) {
height = Integer.valueOf(args[1].trim()).intValue();
} else {
System.out.println("Please enter an integer for your height that is between 1 and 10.");
System.exit(1);
}
List<Row> allRows = new ArrayList<Row>(); // Holds all the possible rows and needed information
findAllRows(width, 0, 0, allRows);
findMatches(allRows);
long totalTables = findUniqueTables(allRows, height);
System.out.println(totalTables);
}
}
/**
* Recursively calculates all possible row combinations for supplied width.
* Row configuration is stored in binary format with 1 indicating gaps. Each bit is
* represented by 3 inches. The bits 1, 2, nth are dropped as they are not needed.
*
* i.e. width of 12 would produce
* width = 12 * 2 = 24
*
* Bricks Binary Stored Binary Decimal Value
* 6 x 6 x 6 x 6 0 1 0 1 0 1 0 1 1 0 1 0 1 21
* 9 x 9 x 6 0 0 1 0 0 1 0 1 0 1 0 0 1 9
* 9 x 6 x 9 0 0 1 0 1 0 0 1 0 1 0 1 0 10
* 6 x 9 x 9 0 1 0 0 1 0 0 1 1 0 0 1 0 18
*/
public static void findAllRows(int width, int currLen, int rowConfig, List<Row> root) {
if (currLen + 6 == width) {
root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
return;
} else if (currLen + 9 == width) {
rowConfig = rowConfig << 1;
root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
return;
} else if (currLen + 6 > width) {
return; // Current configuration is longer than the width is allowed. Do not add.
} else {
int nextConfig = (rowConfig << 2) + 1; //
findAllRows(width, currLen + 6, nextConfig, root);
nextConfig = (rowConfig << 3) + 1;
findAllRows(width, currLen + 9, nextConfig, root);
}
return;
}
/**
* Finds all possible row matches for the given row that do not have gaps that line up.
*/
public static void findMatches(List<Row> rows) {
for (Row row : rows) {
for (Row rowC : rows) {
if (matchesBelow(row.getGaps(), rowC.getGaps())) {
row.addChilcRows(rowC.getGaps());
}
}
}
}
/**
* Does a bitwise AND to see if there are any gaps that line up. If there are no gaps then
* the resulting AND should equal to 0.
*/
public static boolean matchesBelow(int row, int rows) {
if ((row & rows) == 0) {
return true;
} else {
return false;
}
}
/**
* Finds all the unique tables and returns the count.
*/
public static long findUniqueTables(List<Row> allRows, int height) {
long tableCount = 0;
for (Row row : allRows) {
tableCount += findTables(row, height);
}
return tableCount;
}
/**
* This makes all possible tables.
*/
public static long findTables(Row row, int tableHeight) {
long count;
if (tableHeight == 1) {
return 1;
} else {
count = 0;
for (int i = 0; i < row.getChildRowsSize(row); i++) {
count += findTables(row, tableHeight -1);
}
}
return count;
}
}
还有我的puzzle.Row 类。
package puzzle;
import java.util.ArrayList;
import java.util.List;
public class Row {
int gaps;
int width;
List<Long> potChildRows = new ArrayList<Long>();
public Row(int width, int gaps) {
this.gaps = gaps;
this.width = width;
}
public int getGaps() {
return this.gaps;
}
public int getWidth() {
return this.width;
}
public long getChildRowsSize(Row row) {
return row.potChildRows.size();
}
public void addChilcRows(long row) {
this.potChildRows.add(row);
}
}