chess.java

此程序是关于算法设计与分析中的棋盘覆盖问题

/*
 * Created on 2006-2-21
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */

/**
 * @author xsj1
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
import javax.swing.*;
import java.awt.*;

//图形显示棋盘覆盖类
class ShowChess extends JFrame{
	
	public int chesssize;//棋盘规格
	public int chessboard[][];//棋盘
	public int chessdr,chessdc;//特殊方格所在行号和列号 
	
	public ShowChess( int board[][] ,int size,int dr,int dc){
		
		super("Show the Chess");
		chesssize = size;
		chessboard = board;
		chessdr = dr;
		chessdc = dc;
	}
	
	public void showChess(){
		
		int flag=0;//区分棋盘中L型骨牌的颜色标示
		
		Container container = getContentPane();
		container.setLayout(new GridLayout(chesssize, chesssize));
	    this.setTitle("当前棋盘大小为："+chesssize+" * "+chesssize);
	    
		for (int i = 0; i < chesssize; i++) {
			for (int j = 0; j < chesssize; j++) {
				Button button;
				
				flag = chessboard[i][j] % 4;
				
				//显示特殊方格
				if (chessdc == j && chessdr == i) {
					button = new Button();
					button.setBackground(new Color(255, 255, 255));
					button.setLabel("特殊方格");
					button.setSize(10,10);
					container.add(button);
					continue;
				}
				
				switch(flag){
				case 0:
					button = new Button();
					button.setBackground(Color.red);
					button.setLabel(String.valueOf(chessboard[i][j]));
					button.setSize(10,10);
					container.add(button);
					break;
				case 1:
					button = new Button();
					button.setBackground(Color.green);
					button.setLabel(String.valueOf(chessboard[i][j]));
					button.setSize(10,10);
					container.add(button);
					break;
				case 2:
					button = new Button();
					button.setBackground(Color.blue);
					button.setLabel(String.valueOf(chessboard[i][j]));
					button.setSize(10,10);
					container.add(button);
					break;
				case 3:
					button = new Button();
					button.setBackground(Color.yellow);
					button.setLabel(String.valueOf(chessboard[i][j]));
					button.setSize(10,10);
					container.add(button);
					break;
				}
			}
		}
		setSize(400,200);
		setVisible(true);
		pack();
	}
}


public class Chess {

	//tile是用来表示L型骨牌的编号，初始值为0
	public int tile=0;
	
	//chesssize为棋盘的规格：2的random次方
	int random = (int)(Math.random()*5);
	int chesssize = (int)Math.pow(2, random);
	
	//board表示棋盘
    int board[][]=new int[chesssize][chesssize];
    
    /*参数tr：棋盘左上角方格的行号
     * 参数tc：棋盘左上角方格的列号
     * 参数dr：特殊方格所在的行号
     * 参数dc：特殊方格所在的列号
     * 参数size：2的k次方，棋盘规格为2的k次方*2的k次方
     */
	public void chessBoard(int tr,int tc,int dr,int dc,int size)
	{
		if(size==1)return;
		
		int t=tile++;//L型骨牌号
		int s=size/2;//分割棋盘

//	覆盖左上角棋盘
	if(dr<tr+s&&dc<tc+s)
//	特殊方格在此棋盘中
		chessBoard(tr,tc,dr,dc,s);
	
	else
	{//此棋盘中无特殊方格
		System.out.println("1:		"+"tr="+tr+" tc="+tc+
		" dr="+dr+" dc="+dc+" size="+size);
//	用t号L型骨牌覆盖右下角
		board[tr+s-1][tc+s-1]=t;
		System.out.println("第"+(tr+s-1)+"行的第"+(tc+s-1)+"列的值为:"+board[tr+s-1][tc+s-1]);
//	覆盖其余方格
		chessBoard(tr,tc,tr+s-1,tc+s-1,s);
	}

//	覆盖右上角子棋盘
	if(dr<tr+s&&dc>=tc+s)
//	特殊方格在此棋盘中
		chessBoard(tr,tc+s,dr,dc,s);
	else
	{
//	此棋盘中无特殊方格
	    System.out.println("2:		"+"tr="+tr+" tc="+tc+
	    " dr="+dr+" dc="+dc+" size="+size);
//	用t号L型骨牌覆盖左下角
		board[tr+s-1][tc+s]=t;
		System.out.println("第"+(tr+s-1)+"行的第"+(tc+s)+"列的值为:"+board[tr+s-1][tc+s]);
//	覆盖其余方格
		chessBoard(tr,tc+s,tr+s-1,tc+s,s);
	}

//	覆盖左下角棋盘
	if(dr>=tr+s&&dc<tc+s)
//	特殊方格在此棋盘中
		chessBoard(tr+s,tc,dr,dc,s);
	else
	{
//	此棋盘中无特殊方格
	    System.out.println("3:		"+"tr="+tr+" tc="+tc+
	    " dr="+dr+" dc="+dc+" size="+size);
//	用t号L型骨牌覆盖右上角
		board[tr+s][tc+s-1]=t;
		System.out.println("第"+(tr+s)+"行的第"+(tc+s-1)+"列的值为:"+board[tr+s][tc+s-1]);
//	覆盖其余方格
		chessBoard(tr+s,tc,tr+s,tc+s-1,s);
	}

//	覆盖右下角棋盘
	if(dr>=tr+s&&dc>=tc+s)
//	特殊方格在此棋盘中
		chessBoard(tr+s,tc+s,dr,dc,s);
	else
	{
//	此棋盘中无特殊方格
	    System.out.println("4:		"+"tr="+tr+" tc="+tc+
	    " dr="+dr+" dc="+dc+" size="+size);
//	用t号L型骨牌覆盖左上角
		board[tr+s][tc+s]=t;
		System.out.println("第"+(tr+s)+"行的第"+(tc+s)+"列的值为:"+board[tr+s][tc+s]);
//	覆盖其余方格
		chessBoard(tr+s,tc+s,tr+s,tc+s,s);}
	}

	//显示不同规格不同特殊方格下的棋盘覆盖
	public void tiling(int chesssize)
	{
	int i,j;
	int size = chesssize;//棋盘的规格
	int tr=0,tc=0;//左上角方格所在棋盘的位置
	int dr=0,dc=0;//特殊方格所在棋盘的位置
	dr=(int)(Math.random()*size)-1;
	dc=(int)(Math.random()*size)-1;
	System.out.println("特殊方格的位置为：dr="+dr+" dc="+dc);	
	
	System.out.println("当前的棋盘大小为："+size+" * "+size);
        System.out.println("覆盖该棋盘所需要的L型骨牌数目为："+(size*size-1)/3);
	chessBoard(tr,tc,dr,dc,size);
	
	for(i=0;i<size;i++)
	{
		for(j=0;j<size;j++)
			System.out.print(board[i][j]);
		System.out.println();
	}
	
	ShowChess show = new ShowChess(board,size,dr,dc);//图形显示棋盘覆盖结果的类实例
	show.showChess();
	show.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}
	
	public static void main(String[] args) {
		
		Chess c=new Chess();
		c.tiling(c.chesssize);
	}
}