作者在 2012-04-12 21:06:24 发布以下内容
棋盘覆盖问题（图形化显示）：
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JColorChooser;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;
public class ChessBoard extends JFrame implements ActionListener{
ChessBoardPanel chessBoardPanel;
JMenuBar jMenuBar;
JMenu jMenu_color,jMenu;
JMenuItem jMenuItem,jMenuItem2,jMenuItem3,jMenuItem0,jMenuItem6,jMenuItem1;
static Color [] colors={Color.red,Color.green,Color.orange,Color.pink,Color.cyan};
int size=3;
int dr=0,dc=1;
public ChessBoard(){
setTitle("棋盘覆盖——静态显示");
chessBoardPanel=new ChessBoardPanel(size,dr,dc,colors);
jMenuBar=new JMenuBar();
jMenu=new JMenu("菜单");
jMenu_color=new JMenu("改变绘图颜色");
jMenuItem1=new JMenuItem("左上L型颜色");
jMenuItem2=new JMenuItem("左下L型颜色");
jMenuItem3=new JMenuItem("右上L型颜色");
jMenuItem6=new JMenuItem("右下L型颜色");
jMenuItem0=new JMenuItem("初始覆盖点颜色");
jMenuItem=new JMenuItem("设定");
jMenu.setForeground(Color.blue);
jMenu_color.setForeground(Color.blue);
jMenu_color.add(jMenuItem0);
jMenu_color.add(jMenuItem1);
jMenu_color.add(jMenuItem2);
jMenu_color.add(jMenuItem3);
jMenu_color.add(jMenuItem6);
jMenu.add(jMenuItem);
jMenuBar.add(jMenu);
jMenuBar.add(jMenu_color);
jMenuItem.addActionListener(this);
jMenuItem0.addActionListener(this);
jMenuItem1.addActionListener(this);
jMenuItem2.addActionListener(this);
jMenuItem3.addActionListener(this);
jMenuItem6.addActionListener(this);
this.setJMenuBar(jMenuBar);
add(chessBoardPanel);
setSize(768+17,512+65);
setLocation(300,50);
setVisible(true);
setDefaultCloseOperation(EXIT_ON_CLOSE);
chessBoardPanel.board(0, 0, dr, dc, chessBoardPanel.size);
}
public static void main(String args[]){
ChessBoard chessBoard=new ChessBoard();
}
@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
if (e.getSource()==jMenuItem) {
System.out.println("xuanzhong");
String regex="[ ]+";
String arraysString[];
String string=new JOptionPane().showInputDialog("请输入2的指数k，即2的k次方作为size\n(size理论值要小于int型表示范围/3)\n和初始覆盖点坐标(x，y),\n所有参数用空格隔开：");
arraysString=string.split(regex);
size=Integer.parseInt(arraysString[0]);
dr=Integer.parseInt(arraysString[1]);
dc=Integer.parseInt(arraysString[2]);
System.out.println(size);
}else if (e.getSource()==jMenuItem0) {
colors[0]=JColorChooser.showDialog(this, "选择初始覆盖点颜色", Color.red);
}else if (e.getSource()==jMenuItem1) {
colors[1]=JColorChooser.showDialog(this, "选择左上L型颜色", Color.red);
}else if (e.getSource()==jMenuItem2) {
colors[2]=JColorChooser.showDialog(this, "选择左下L型颜色", Color.red);
}else if (e.getSource()==jMenuItem3) {
colors[3]=JColorChooser.showDialog(this, "选择右上L型颜色", Color.red);
}else if (e.getSource()==jMenuItem6) {
colors[4]=JColorChooser.showDialog(this, "选择右下L型颜色", Color.red);
}
//更新画面
{
remove(chessBoardPanel);
chessBoardPanel = new ChessBoardPanel(size, dr, dc, colors);
add(chessBoardPanel);
chessBoardPanel.board(0, 0, dr, dc, chessBoardPanel.size);
chessBoardPanel.repaint();
setVisible(true);
}
}
}
class ChessBoardPanel extends JPanel{
int [][] chessmap;
int size;
int length;
static int x=1;
int dr,dc;
Color [] colors;
public ChessBoardPanel(int k,int dr,int dc, Color [] colors) {
// TODO Auto-generated constructor stub
size = (int) Math.pow(2, k);
length = 512 / size;
chessmap = new int[size][size];
//initmap();
this.colors=colors;
this.dr=dr;
this.dc=dc;
}
public void initmap(){
chessmap = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j <size; j++) {
chessmap[i][j]=0;
}
}
}
public void board(int mr,int mc,int dr,int dc,int size){
if (size==1) {
return;
}
int s=size/2;
int d=x++;
//左上
if (dr<mr+s&&dc<mc+s) {
board(mr, mc, dr, dc, s);
}else {
chessmap[mr+s-1][mc+s-1]=d;
board(mr, mc, mr+s-1, mc+s-1, s);
}
//右上
if (dr<mr+s&&dc>=mc+s) {
board(mr, mc+s, dr, dc, s);
}else {
chessmap[mr+s-1][mc+s]=d;
board(mr, mc+s, mr+s-1, mc+s, s);
}
//左下
if (dr>=mr+s&&dc<mc+s) {
board(mr+s, mc, dr, dc, s);
}else {
chessmap[mr+s][mc+s-1]=d;
board(mr+s, mc, mr+s, mc+s-1, s);
}
//右下
if (dr>=mr+s&&dc>=mc+s) {
board(mr+s, mc+s, dr, dc, s);
}else {
chessmap[mr+s][mc+s]=d;
board(mr+s, mc+s, mr+s, mc+s, s);
}
//System.out.println(String.valueOf(color_flag));
}
public void printTheChess() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(chessmap[i][j]+" ");
}
System.out.println();
}
}
public void paint(Graphics g){
System.out.println("paint");
printTheChess();
g.setColor(Color.white);
g.fillRect(0, 0, 512, 512);
g.setColor(Color.lightGray);
g.fillRect(512, 0, 256, 512);
g.setColor(Color.black);
//画边框
g.drawLine(0+1, 0+1, 512, 0+1);
g.drawLine(0+1, 0+1, 0+1, 512);
g.drawLine(512, 0, 512, 512);
g.drawLine(0, 512, 512, 512);
//最右侧分割线
g.drawLine(760, 0, 760, 512);
int sub=(int)(length*0.1);
for (int i = 0; i < size-1; i++) {
for (int j = 0; j <size-1; j++) {
if (chessmap[i][j]==0) {//如果该点是初始覆盖点，画出该点，并画出它右下角的L型
g.setColor(colors[0]);
g.fill3DRect(j*length, i*length, length, length,true);
if(chessmap[i+1][j+1]==chessmap[i+1][j]&&chessmap[i+1][j+1]==chessmap[i][j+1]){
g.setColor(colors[4]);
g.fill3DRect((j+1)*length, (i+1)*length, length, length,true);
g.fill3DRect((j+1)*length, i*length, length, length,true);
g.fill3DRect(j*length, (i+1)*length, length, length,true);
//去掉l图形中的划分
g.fillRect((j+1)*length, i*length, length-1, length+sub);
g.fillRect(j*length, (i+1)*length, length+sub, length-1);
/*//写上标号
g.setColor(Color.red);
g.drawString("A",(int)((j+1+0.5)*length), (int)((i+1+0.5)*length));*/
}
}else if (chessmap[i][j]==chessmap[i+1][j]&&chessmap[i][j]==chessmap[i][j+1]) {//画出左上L型
g.setColor(colors[1]);
g.fill3DRect(j*length, i*length, length, length,true);
g.fill3DRect((j+1)*length, i*length, length, length,true);
g.fill3DRect(j*length, (i+1)*length, length, length,true);
//去掉l图形中的划分
g.fillRect(j*length, i*length, length+sub, length);
g.fillRect(j*length, i*length, length, length+sub);
/*//写上标号
g.setColor(Color.black);
g.drawString("B",(int)((j+0.5)*length), (int)((i+0.5)*length));*/
}else if (chessmap[i][j]==chessmap[i+1][j]&&chessmap[i][j]==chessmap[i+1][j+1]) {//画出左下L型
g.setColor(colors[2]);
g.fill3DRect(j*length, i*length, length, length,true);
g.fill3DRect((j+1)*length, (i+1)*length, length, length,true);
g.fill3DRect(j*length, (i+1)*length, length, length,true);
//去掉l图形中的划分
g.fillRect(j*length, (i+1)*length-sub, length, length);
g.fillRect(j*length+sub, (i+1)*length, length, length);
/*//写上标号
g.setColor(Color.blue);
g.drawString("C",(int)((j+0.5)*length), (int)((i+1+0.5)*length));*/
}else if (chessmap[i][j]==chessmap[i][j+1]&&chessmap[i][j]==chessmap[i+1][j+1]) {//画出右上L型
g.setColor(colors[3]);
g.fill3DRect(j*length, i*length, length, length,true);
g.fill3DRect((j+1)*length, i*length, length, length,true);
g.fill3DRect((j+1)*length, (i+1)*length, length, length,true);
//去掉l图形中的划分
g.fillRect((j+1)*length-sub, i*length, length-1, length-1);
g.fillRect((j+1)*length, i*length+sub, length-1, length-1);
/*//写上标号
g.setColor(Color.green);
g.drawString("D",(int)((j+1+0.5)*length), (int)((i+0.5)*length));*/
j++;//可以跳过下个扫描点
}else if (chessmap[i+1][j]==chessmap[i][j+1]&&chessmap[i+1][j]==chessmap[i+1][j+1]) {//画出右下L型
g.setColor(colors[4]);
g.fill3DRect((j+1)*length, (i+1)*length, length, length,true);
g.fill3DRect((j+1)*length, i*length, length, length,true);
g.fill3DRect(j*length, (i+1)*length, length, length,true);
//去掉l图形中的划分
g.fillRect((j+1)*length, i*length, length-1, length+sub);
g.fillRect(j*length, (i+1)*length, length+sub, length-1);
/*//写上标号
g.setColor(Color.red);
g.drawString("A",(int)((j+1+0.5)*length), (int)((i+1+0.5)*length));*/
j++;//可以跳过下个扫描点
}
}
}
//扫描最后一行是否有初始覆盖点
for (int i = 0; i < size; i++) {
if(chessmap[size-1][i]==0){
g.setColor(colors[0]);
g.fill3DRect(i*length, (size-1)*length, length, length,true);
}
}
//扫描最后一列是否有初始覆盖点
for (int i = 0; i < size; i++) {
if(chessmap[i][size-1]==0){
g.setColor(colors[0]);
g.fill3DRect((size-1)*length, i*length, length, length,true);
}
}
//画提示信息
g.setColor(Color.blue);
x=512+2;
String sizeString="当前规模是"+String.valueOf(size)+"×"+String.valueOf(size);
String sizeString1="初始覆盖点坐标： ("+String.valueOf(dr)+","+String.valueOf(dc)+")";
g.drawString("这是棋盘覆盖的静态显示通过递归分治算法：", x, 60);
g.drawString(" 红色区域表示初始覆盖点,绿色区域表示左", x, 90);
g.drawString("上L型,粉红色区域表示右上L型,橘黄色区域表", x, 120);
g.drawString("示左下L型,青色区域表示左上L型。(默认)", x, 150);
g.setColor(new Color(111,1,1));
g.drawString(sizeString, x, 200);
g.drawString(sizeString1, x, 250);
g.setColor(Color.red);
g.drawString(" 注意当规模大于512×512之后,图形将无",x,300);
g.drawString("法显示出来,但后台程序仍可以继续运行！",x,330);
}
}
如何应用分治法求解棋盘覆盖问题呢？分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0时，可将2^k×2^k的棋盘划分为4个2^（k-1）×2^（k-1）的子棋盘，如图4.11(a)所示。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图4.11(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。
（分析引自百度百科）
