knightcruise.java

算法分析实验 java实现： 有： 公约数 合并算法 字符排序 快速排序 马踏棋盘问题 马踏棋盘问题（文本做法） 折半查找 最大子段和

import java.applet.Applet;
import javax.swing.JOptionPane;
import java.awt.*;
import java.awt.event.*;

//提供二元型数值
class Pair
{
      private int x;
      private int y;
      Pair()
      {
      }
      Pair(int a,int b)
      {
         x=a;
         y=b;
      }
     public int getX()
     {
         return x;
     }
     public int getY()
     {
         return y;
     }
}

//提供巡游结果
class GetKnightCruise
  
{
                         //存储8*8棋盘上各位置为第几步
     private static int[][] arr=new int[8][8];
                         //用来存储骑士可以到达的8个位置的偏移量
     private static Pair[] index=new Pair[8];
                          //设置index的初始值
     int a,b;
     private static void setIndex()
     {
           index[0]=new Pair(-2,1);
           index[1]=new Pair(-1,2);
           index[2]=new Pair(1,2);
           index[3]=new Pair(2,1);
           index[4]=new Pair(2,-1);
           index[5]=new Pair(1,-2);
           index[6]=new Pair(-1,-2);
           index[7]=new Pair(-2,-1);
     }
                         //设置棋盘位置的处始值
     private static void setArr()
     {
           for (int i=0;i<8;i++)
           {
                 for (int j=0;j<8;j++)
                 {
                       arr[i][j]=0;
                 }
           }
     }
                        //计算位置（i,j）的出口数
     private static int getExitNum(int i,int j)
     {
           int num=0;
           for(int t=0;t<8;t++)
           {
                  if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
                  {
                         num++;
                  }
           }
           return num;
     }
                //选择下一个所走的位置，beginIndex的作用是定位选择优先权的起始位置
     private static Pair getNextPositioin(int i,int j,int beginIndex)
     {
           int[] temp=new int[8];
           int min=8;
           for(int t=0;t<8;t++)
           {
                   if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
                   {
                         temp[t]=getExitNum(i+index[t].getX(),j+index[t].getY());
                         if(temp[t]!=0&&temp[t]<min)
                         {
     min=temp[t];
    }
   }
  }
  for(int t=0;t<8;t++)
  {
   int h=(t+beginIndex)%8;
   if(temp[h]==min)
   {
    return new Pair(i+index[h].getX(),j+index[h].getY());
   }
  }
  return new Pair(-1,-1);
 }
 //寻找下一个唯一的出口（主要给最后一步使用，因为getNextPositioin已经不适合了）
 private static Pair getNextPositioinOfTheLastStep(int i,int j)
 {
  for(int t=0;t<8;t++)
  {
   if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
   {
    return new Pair(i+index[t].getX(),j+index[t].getY());
   }
  }
  return new Pair(-1,-1);
  
 }
 //从（i,j）开始骑士巡游
static int[][] getKnightCruise(int i,int j)
 { 
  Pair tt;
  setArr();
  setIndex();
  for(int q=0;q<8;q++)
  {
   int ii=i,jj=j;
   int p=0;
   for(p=1;p<=64;p++)
   {
    arr[ii][jj]=p;
    if(p==63)
    {
     tt=getNextPositioinOfTheLastStep(ii,jj);
     ii=tt.getX();
     jj=tt.getY();
     continue;
    }
    tt=getNextPositioin(ii,jj,p);
    ii=tt.getX();
    jj=tt.getY();
    if(ii==-1||jj==-1)
    {
     break;
    }
   }
   if(p==65)
   {
    return arr; 
   }
  }
    return arr;
 }
 //得到巡游数组
 public static int[][] getResult()
 {
  int i=1,j=1;
  getKnightCruise(i,j);
  return arr;
 }
}


public class KnightCruise extends Applet implements ActionListener
{   
    boolean flag=false;
    int a,b;
    TextField tf1,tf2;
    Label lb1,lb2;
    Button bt1;
    public void init(){
	lb1=new Label("i:");
        lb2=new Label("j:");
	tf1=new TextField(3);
        tf2=new TextField(3);
        bt1=new Button("确定");
        add(lb1);add(tf2);add(lb2);add(tf1);add(bt1);
        bt1.addActionListener(this);
    }
    public void paint(Graphics g)
    {
    if(flag){
  	for(int i=1;i<=8;i++)
  	{
   		for(int j=1;j<=8;j++)
	   	{
    			if((((i%2)==1)&&((j%2)==0))||(((i%2)==0)&&((j%2)==1)))
    			{
     				g.setColor(Color.red);
     				g.fillRect(i*40,j*40,40,40);
    			}
    			else
    			{
     				g.setColor(Color.white);
     				g.fillRect(i*40,j*40,40,40);
    			}
   		}
  	}
  	g.setColor(Color.blue);
  	for(int i=0;i<8;i++)
  	{
   		for(int j=0;j<8;j++)
   		{
    			g.drawOval(48+i*40,48+j*40,24,24);
   		}
  	}
        g.setColor(Color.black);
  	int[][] board=new int[8][8];
  	board=GetKnightCruise.getKnightCruise(a,b);
  	Font num=new Font("宋体",Font.BOLD,15);
  	g.setFont(num);
  	for(int i=0;i<8;i++)
  	{
   		for(int j=0;j<8;j++)
   		{
    			g.drawString(board[i][j]+"",53+i*40,65+j*40);
                        
   		}
  	}
        return;
       }
   }
   public void actionPerformed(ActionEvent e){
       a=Integer.parseInt(tf1.getText());
       b=Integer.parseInt(tf2.getText());
       flag=true;
       repaint();
   }
}