棋盘覆盖
程序员文章站
2024-01-17 09:09:52
...
下面介绍的是棋盘覆盖问题
采用的分治算法
算法如下
tr :棋盘左上角的行号
td 棋盘左上角的列号
dr:特殊方格所在的行号
dc :特殊方格所在的列号
sizes=2的k次方 棋盘规格为sizes*sizes
public void chessBoard(int tr,int tc,int dr,int dc,int sizes)
{
if(sizes==1)
return ;
int s=sizes/2;
int t=count++;
//特殊点在左上角
if(dr<tr+s&&dc<tc+s)
{
chessBoard(tr,tc,dr,dc,s);
}
else
{
board[tr+s-1][tc+s-1]=t;
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
{
board[tr+s-1][tc+s]=t;
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
{
board[tr+s][tc+s-1]=t;
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
{
board[tr+s][tc+s]=t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}完整的java 代码如下
Main
package com.qipan.main;
import java.awt.Color;
import java.awt.GridLayout;
import java.util.ArrayList;
import javax.swing.BorderFactory;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class Main{
public static void main(String args[])
{
ArrayList<MyJPanel> list;
Tool tool=new Tool();
tool.duWork();
int [][]board=tool.getBoard();
JFrame jframe=new JFrame("棋盘覆盖");
jframe.setSize(500, 500);
jframe.setLayout(new GridLayout(tool.getSize(), tool.getSize(), 0, 0));
jframe.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
jframe.setLocationRelativeTo(null);
list=new ArrayList<MyJPanel>();
for(int i=0;i<tool.getSize();i++)
{
for(int j=0;j<tool.getSize();j++)
{
MyJPanel buttonPanel = new MyJPanel(board[i][j]);
buttonPanel.setMyX(i);
buttonPanel.setMyY(j);
list.add(buttonPanel);
buttonPanel.setBorder(BorderFactory.createLineBorder(Color.red));
jframe.add(buttonPanel);
buttonPanel.setArrayList(list);
}
}
jframe.setVisible(true);
}
}
自定义的一个JPanel
package com.qipan.main;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import javax.swing.JLabel;
import javax.swing.JPanel;
public class MyJPanel extends JPanel {
private JLabel jl;
private boolean flag=false;//记录是否已经显示JLabel；
private int number;
private int x;
private int y; //JPanel的位置；
private int size=PublicSize.size;//棋盘的大小
private static ArrayList <MyJPanel> list;
public void setArrayList(ArrayList<MyJPanel> list)
{
this.list=list;
}
public int getMyX() {
return x;
}
public void setMyX(int x) {
this.x = x;
}
public int getMyY() {
return y;
}
public void setMyY(int y) {
this.y = y;
}
public int getNumber()
{
return number;
}
public JLabel getJLabel()
{
return jl;
}
public MyJPanel(int number)
{
jl=new JLabel();
this.number=number;
this.add(jl);
this.addMouseListener(ma);
//this.addActionListener(this);
}
MouseAdapter ma=new MouseAdapter() {
public void mouseClicked(MouseEvent e) {
jl.setText(String.valueOf(number));
//上
if(x-1<0)
{
;
}else
{
MyJPanel mj=list.get((x-1)*size+y);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("上");
}
}
//左上
if(x-1<0||y-1<0)
{
;
}else
{
MyJPanel mj=list.get((x-1)*size+y-1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("左上");
}
}
//右上
if(x-1<0||y+1>=size)
{
;
}else
{
MyJPanel mj=list.get((x-1)*size+y+1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("右上");
}
}
//下
if(x+1>=size)
{
;
}else
{
MyJPanel mj=list.get((x+1)*size+y);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("下");
}
}
//左
if(y-1<0)
{
;
}else
{
MyJPanel mj=list.get((x)*size+y-1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("左");
}
}
//右
if(y+1>=size)
{
;
}else
{
MyJPanel mj=list.get((x)*size+y+1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("右");
}
}
//左下
if(y-1<0||x+1>=size)
{
;
}else
{
MyJPanel mj=list.get((x+1)*size+y-1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("左下");
}
}
//右下
if(y+1>=size||x+1>=size)
{
;
}else
{
MyJPanel mj=list.get((x+1)*size+y+1);
int number2=mj.getNumber();
if(number==number2)
{
mj.getJLabel().setText(number+"");
System.out.println("右下");
}
}
};
};
}
存放公共长度的类 PublicSize
package com.qipan.main;
public class PublicSize {
public static final int size=16;
}
工具类
package com.qipan.main;
public class Tool {
private int k=3;
private int size=PublicSize.size;
int board[][]=new int[size][size];
int count=1;
private int x=0;
private int y=1;
public int[][] getBoard()
{
return board;
}
public int getSize()
{
return size;
}
public void setSize(int size)
{
this.size=size;
}
//分治算法ChessBoard
public void chessBoard(int tr,int tc,int dr,int dc,int sizes)
{
if(sizes==1)
return ;
int s=sizes/2;
int t=count++;
//特殊点在左上角
if(dr<tr+s&&dc<tc+s)
{
chessBoard(tr,tc,dr,dc,s);
}
else
{
board[tr+s-1][tc+s-1]=t;
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
{
board[tr+s-1][tc+s]=t;
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
{
board[tr+s][tc+s-1]=t;
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
{
board[tr+s][tc+s]=t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}
public void disPlay(int a[][])
{
System.out.println(size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
}
public void duWork()
{
setSize(size);
//System.out.println(getSize()+">>>>");
chessBoard(0, 0, x, y, getSize());
disPlay(board);
}
}