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);
}
}