|
這是網上搜的java程序- -!
Triomino問題，即用一個L形的瓦片（有三個小正方形組成）覆蓋一個缺少了一個方塊（可以是棋盤上的 任何位置）的2^n X 2^n棋盤
Triomino問題的動態演示程序。
源代碼：
用分治法解triomino問題
public void trio(int x, int y, int cStart, int cEnd, int rStart, int rEnd)
{
if(cEnd - cStart > 1)
{
if(x> =cStart && x <=(cEnd+cStart)/2 && y> =rStart && y <=(rEnd+rStart)/2)
{
trio(x, y, cStart, (cEnd+cStart)/2, rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2, (cEnd+cStart)/2+1, cEnd,
rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, (cEnd+cStart)/2+1, cEnd,
(rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2+1, cStart, (cEnd+cStart)/2,
(rEnd+rStart)/2+1, rEnd);
/*fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.black);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.black);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1, Color.black);*/
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 3;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 3;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 3;
pause();
repaint();}
if(x <=cEnd && x> (cEnd+cStart)/2 && y> =rStart && y <=(rEnd+rStart)/2)
{
trio(x, y, (cEnd+cStart)/2+1, cEnd, rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, (cEnd+cStart)/2+1, cEnd,
(rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2+1, cStart, (cEnd+cStart)/2,
(rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2, cStart, (cEnd+cStart)/2,
rStart, (rEnd+rStart)/2);
/*fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.black);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1,Color.black);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.black);*/
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 3;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 3;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 3;
pause();
repaint(); }
if(x <=cEnd && x> (cEnd+cStart)/2 && y <=rEnd && y> (rEnd+rStart)/2)
{
trio(x, y, (cEnd+cStart)/2+1, cEnd, (rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2+1, cStart, (cEnd+cStart)/2,
(rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2, cStart, (cEnd+cStart)/2,
rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2, (cEnd+cStart)/2+1, cEnd,
rStart, (rEnd+rStart)/2);
/*fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1, Color.black);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.black);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.black);*/
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 3;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 3;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 3;
pause();
repaint(); }
if(x> =cStart && x <=(cEnd+cStart)/2 && y <=rEnd && y> (rEnd+rStart)/2)
{
trio(x, y, cStart, (cEnd+cStart)/2, (rEnd+rStart)/2+1, rEnd);
trio((cEnd+cStart)/2, (rEnd+rStart)/2, cStart, (cEnd+cStart)/2,
rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2, (cEnd+cStart)/2+1, cEnd,
rStart, (rEnd+rStart)/2);
trio((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, (cEnd+cStart)/2+1, cEnd,
(rEnd+rStart)/2+1, rEnd);
/*fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.black);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.black);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.black);*/
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 3;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 3;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 3;
pause();
repaint(); }}
else
{
if(x> =cStart && x <=(cEnd+cStart)/2 && y> =rStart && y <=(rEnd+rStart)/2)
{
/*fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.red);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.red);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1, Color.red);*/
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 1;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 1;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 1;
pause();
repaint();}
if(x <=cEnd && x> (cEnd+cStart)/2 && y> =rStart && y <=(rEnd+rStart)/2)
{
/*fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.green);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1,Color.green);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.green);*/
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 2;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 2;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 2;
pause();
repaint();}
if(x <=cEnd && x> (cEnd+cStart)/2 && y <=rEnd && y> (rEnd+rStart)/2)
{
/*fillRect((cEnd+cStart)/2, (rEnd+rStart)/2+1, Color.red);
fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.red);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.red);*/
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2+1] = 1;
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 1;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 1;
pause();
repaint(); }
if(x> =cStart && x <=(cEnd+cStart)/2 && y <=rEnd && y> (rEnd+rStart)/2)
{
/*fillRect((cEnd+cStart)/2, (rEnd+rStart)/2, Color.green);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2, Color.green);
fillRect((cEnd+cStart)/2+1, (rEnd+rStart)/2+1, Color.green);*/
chessBoard[(cEnd+cStart)/2][(rEnd+rStart)/2] = 2;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2] = 2;
chessBoard[(cEnd+cStart)/2+1][(rEnd+rStart)/2+1] = 2;
pause();
repaint();
}}}
public void run()
{ trio(x, y, 1, 8, 1, 8);}
public void pause()
{try
{ Thread.sleep(1000);
} catch (InterruptedException e){}}
public void fillRect(int x, int y, Color color)
{ Graphics2D g2D = (Graphics2D)getGraphics();
g2D.setPaint(color);
g2D.fill(new Rectangle2D.Float(10.0f+18*x, 40.0f+18*y, 15.0f, 15.0f));
}
}
|
加好友 
發短信
Post By：2010-12-11 9:27:09
