我已經得到了2^k * 2^k大小的棋盤,其中一塊棋子隨機移除,使它成爲一個不足的棋盤。任務是填充由3塊瓷磚組成的L形圖案「trominos」。分而治之算法
解決它的過程並不困難。如果板子是2x2,那麼只需要一個tromino來填充它。對於任何更大的尺寸,它必須分成四個等分(製作四個2 ^(k-1)大小的棋盤),一個tromino放置在中心點,因此每個象限都有一個填充了瓷磚。之後,董事會可以遞歸填充,直到每個瓷磚填充隨機彩色tromino。
我的主要問題是實際執行代碼。我在Java編程方面的技能通常非常薄弱,我經常遇到麻煩,找到一個開始的地方。唯一要完成的工作是在平鋪類中的平鋪方法中,該方法將缺陷板作爲輸入,將行和列開始平鋪,並填充平鋪的數量。這是一個家庭作業問題,所以我只是尋找一些指導或地方開始 - 任何幫助將不勝感激。
public class BoardViewer extends JFrame {
private static final int WIDTH = 1024;
private static final int HEIGHT = 768;
private static final int OFFSET = 30;
public static final int UPVERT = 1;
public static final int DNVERT = 2;
public static final int RHORIZ = 4;
public static final int LHORIZ = 8;
public static final int FILL = 16;
private Color [][] board;
public BoardViewer(DeficientBoard db) {
super();
setSize(WIDTH + (OFFSET*2), HEIGHT + (OFFSET*2));
setDefaultCloseOperation(EXIT_ON_CLOSE);
setResizable(false);
board = db.getBoardColor();
}
public void paint(Graphics g) {
super.paint(g);
int width = WIDTH/board[0].length;
int height = HEIGHT/board.length;
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[r].length; c++) {
g.setColor(board[r][c]);
int x = c*width + OFFSET;
int y = r*height + OFFSET + (OFFSET/2);
g.fillRect(x+1, y+1, width-1, height-1);
}
}
}
public class DeficientBoard {
private int n;
private Color board[][];
// The four rotations of the tile.
// UL is XX
// X
// UR is XX
// X
// LL is X
// XX
// LR is X
// XX
public final int UL = 0;
public final int UR = 1;
public final int LL = 2;
public final int LR = 3;
/**
* Create a 2^k x 2^k deficient board.
*
* @param k power
*/
public DeficientBoard(int k) {
n = (int)Math.pow(2, k);
createBoard(Color.LIGHT_GRAY);
}
/**
* Actually create an n x n deficient board.
*
* @param color background color
*/
private void createBoard(Color color) {
board = new Color[n][n];
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
board[r][c] = color;
int d_row = (int)(Math.random() * n);
int d_col = (int)(Math.random() * n);
board[d_row][d_col] = Color.BLACK;
}
/**
* Given a row and column and shape based on that point
* place a tromino of the given color.
*
* @param r row
* @param c column
* @param s shape (UL, UR, LL, LR)
* @param theColor a Color
*/
public void placeTromino(int r, int c, int s, Color theColor) {
if (s == UL) {
board[r][c] = theColor;
board[r][c+1] = theColor;
board[r+1][c] = theColor;
} else if (s == UR) {
board[r][c] = theColor;
board[r][c+1] = theColor;
board[r+1][c+1] = theColor;
} else if (s == LL) {
board[r][c] = theColor;
board[r+1][c] = theColor;
board[r+1][c+1] = theColor;
} else {
board[r+1][c] = theColor;
board[r+1][c+1] = theColor;
board[r][c+1] = theColor;
}
}
/**
* Get the 2^k x 2^k board.
*
* @return the Color board.
*/
public Color[][] getBoardColor() {
return board;
}
/**
* Find and return the deficient row.
*
* @param row row
* @param col column
* @param sz size of the baord
* @return the row the deficient block is located
*/
public int getDeficientRow(int row, int col, int sz) {
for (int r = row; r < (row + sz); r++)
for (int c = col; c < (col + sz); c++)
if (board[r][c] != Color.LIGHT_GRAY)
return r;
return -1;
}
/**
* Find and return the deficient column.
*
* @param row row
* @param col column
* @param sz size of the baord
* @return the row the deficient block is located
*/
public int getDeficientCol(int row, int col, int sz) {
for (int r = row; r < (row + sz); r++)
for (int c = col; c < (col + sz); c++)
if (board[r][c] != Color.LIGHT_GRAY)
return c;
return -1;
}
/**
* Get the size of the deficient board.
*
* @return the size
*/
public int getSize() {
return n;
}
/**
* Display information about the deficient board.
*/
public String toString() {
return ("Deficient board of size "
+ n + "x" + n
+ " with position missing at ("
+ getDeficientRow(0, 0, n) + "," + getDeficientCol(0, 0, n) +").");
}
}
public class Tiling {
private static Color randColor() {
int r = (int)(Math.random() * 256);
int g = (int)(Math.random() * 256);
int b = (int)(Math.random() * 256);
return new Color(r, g, b);
}
public static void tile(DeficientBoard db, int row, int col, int n) {
}
public static void main(String[] args) {
DeficientBoard db = new DeficientBoard(3);
System.out.println(db);
tile(db, 0, 0, db.getSize());
BoardViewer bv = new BoardViewer(db);
bv.setVisible(true);
}
}
-1,對不起。你提出的算法遠遠不如OP在問題第二段中描述的算法。我不明白你爲什麼要這麼做,除非你完全誤解了OP的問題。回覆:「如果我正確地理解了這個問題,他就沒有真正寫過*任何*代碼;相反,發佈的代碼是作爲作業問題的一部分提供的,實際的任務是實現'Tiling.tile'。 – ruakh 2013-02-27 17:41:56
嗯,我確實說過我沒有完整的解決方案,我重新閱讀這篇文章,並且沒有提到誰編寫了代碼。 OP所描述的算法沒有足夠的細節來決定如何填寫trominos,或者你必須遞歸地將所有的板劃分爲4x4並解決這些問題,而不是2x2。所以我認爲「極其低劣」有點過於戲劇化,因爲它沒有完全描述。 – chubbsondubs 2013-02-28 01:44:56