2.txt

骑士漫游

import java.util.*;
/*author：方梁康
 Student No.:5050309334
 data:8/19/2007
 function:骑士漫游世界问题，采用贪婪算法。
 新增功能1： “动画”演示功能。你可以在给出答案之后选择是否用动画进行演示。
 新增功能2：你可以选择棋盘大小，考虑到动画演示的屏幕大小以及可能无解问题（这样要递归很久），程序设定棋盘大小为8×8与44×44之间偶数。
*/
public class Knight 
{
	   int knightMap[][];			//记录骑士行走过程中8×8个点的状态
	   int times;					//进入search时表示当前已走的步数
	   int horizontal[]=new int [8];//8移动方法的row方向位移     这里规定row的位置为knightMap[][]的一维下标
	   int vertical[]=new int [8];//8移动方法的column方向位      这里规定column的位置为knightMap[][]的二维下标
	   int move_x[];				//x与row关联                    记录row方向上的位置
	   int move_y[];				//y与column关联                 记录column方向上的位置
	   int currentRow;			 //当前row
	   int currentColumn;		//当前column
	   int moveNumber;			//记录移动8种方法中的一种
	   long findNum;			//记录找到的方法数
	   int flag;				//打印标记
	   int choose;				//结果打印方式
	   int size;
	   Knight(int currentRow,int currentColumn,int size)//构造函数
	   {
		   this.size=size;
		   knightMap=new int [size][size];
		   knightMap[currentRow][currentColumn]=1;
		   move_x=new int[size*size+1];
		   move_y=new int[size*size+1];
		   times=1;
		   choose=0;
		   flag=0;
		   findNum=0;
		   horizontal[0]=2;
		   horizontal[1]=1;
		   horizontal[2]=-1;
		   horizontal[3]=-2;
		   horizontal[4]=-2;
		   horizontal[5]=-1;
		   horizontal[6]=1;
		   horizontal[7]=2;
		   vertical[0]=-1;
		   vertical[1]=-2;
		   vertical[2]=-2;
		   vertical[3]=-1;
		   vertical[4]=1;
		   vertical[5]=2;
		   vertical[6]=2;
		   vertical[7]=1;
		   this.currentRow=move_x[0]=move_x[1]=currentRow;
		   this.currentColumn=move_y[0]=move_y[1]=currentColumn;
	   }

	   int road(int currentRow ,int currentColumn) //指定点有几条路可走
	   {
		   int i=0;
		   int x=0;
		   int y=0;
		   int sum=0;
		   for(i=0;i<8;i++)
		   {
			   x=horizontal[i]+currentRow;
			   y=vertical[i]+currentColumn;
			   if(x>=0&&x<size&&y>=0&&y<size&&knightMap[x][y]==0)//界内
			   sum++ ;
		   }
		   return sum;   
	   }
	   int chooseRoad(int currentRow ,int currentColumn,boolean notChoosed[])//指定点应该优先走哪条路
	   {
		   int i=0;
		   int x=0;
		   int y=0;
		   int leastRoad=9;//优先选择标准。此变量记录下一步可走的众多点当中，哪一个点剩余的路最少，则优先选择该点
		   int road;       //记录指定点剩余的路的条数
		   moveNumber=-1;
		   for(i=0;i<8;i++)
		   {
			   x=horizontal[i]+currentRow;
			   y=vertical[i]+currentColumn;
			   if(x>=0&&x<size&&y>=0&&y<size&&notChoosed[i])//检查界内和此路选过与否
			   {
				   if(knightMap[x][y]==0) 		//检查要走的点是否已经被走过
				   {
					   road=road(x,y);
					   if (leastRoad>road)//优先选择标准
					   {
						   leastRoad=road;
						   moveNumber=i;			   
					   }
				   }
			   }	   
		   }
		   return moveNumber;   
	   }
	   boolean search()
	   {		 
		   boolean notChoosed[]={true,true,true,true,true,true,true,true};
		   int currentMove=0;
		   boolean searchFlag =false;
		   times++;
		   if(times==size*size+1)//递归结束条件
		   {
			   	findNum++;
				searchFlag=true;	
				Scanner scanner;
				if(flag==0)
				{
					System.out.println();
					System.out.println("1:打印一个结果,并且动画演示      2:快速打印下10种方法      3:快速打印下100中方法  (因为递归算法，每个方法的差别表现在尾部)");			
					scanner=new Scanner(System.in);
					choose =scanner.nextInt();	
					while (choose!=1&&choose!=2&&choose!=3)
					{ 
						System.out.println("Mismath,please input again. 输入 1 动画演示, 输入 2 快速打印下10种方法, 输入 3 快速打印下100中方法");
						choose=scanner.nextInt();
					}
				}						
				if(choose==1)
				{
					printMap();//打印结果
				}
				if(choose==2)//快速打印
				{
					if(flag==0)
						flag=10;
					flag--;					
				}
				if(choose==3)//快速打印
				{
					if(flag==0)
						flag=100;
					flag--;
				} 
				System.out.println("第 "+findNum+" 种方法:");	
				//if(findNum==10000)										//在这里可以设置打印第几种方法
				//	printMap();
				System.out.println("骑士本次漫游从("+move_x[1]+","+move_y[1]+")开始，然后(row增量,column增量)的形式漫游");
				for(int i=2;i<size*size+1;i++)
				{
					   System.out.print("("+move_x[i]+","+move_y[i]+") ");
				}
				System.out.println();
		   }		   
		   else
		   {
			   for(int i=0;i<8;i++)
			   {
				   chooseRoad(currentRow ,currentColumn,notChoosed);
				   if(moveNumber==-1)
				   {					   
					   searchFlag=false;					   
				   }
				   else
				   {
					   currentMove=moveNumber;					   
					   move_x[times]=horizontal[moveNumber];
					   move_y[times]=vertical[moveNumber];
					   currentRow+=horizontal[moveNumber];
					   currentColumn+=vertical[moveNumber];
					   knightMap[currentRow][currentColumn]=1;
					   search();								//递归
					   knightMap[currentRow][currentColumn]=0;
					   currentRow-=horizontal[currentMove];
					   currentColumn-=vertical[currentMove];
					   notChoosed[currentMove]=false;
					   if(times==size*size)
						   break;
				   }
			   }			   
		   }	
		   times--;
		   return searchFlag;	   
	   }
	   void printMap()
	   {		  
		   int mapRecord[][]=new int [size][size];
		   System.out.println("*********************************************************************图  1*********************************************************************");
		   for(int i=0;i<size;i++)
		   {
			   for(int j=0;j<size;j++)
			   {		 
				   if(((i==move_x[1])&&(j==move_y[1]))||(mapRecord[i][j]==1))
				   {	
					   if(mapRecord[i][j]==1)
						   System.out.print("#  ");
					   else
					   {
						   System.out.print("$  ");
						   mapRecord[i][j]=1;
					   }
				   }
				   else
					   System.out.print("!  "); 
			   }
			   System.out.println();
		   }
		   for(int k=2;k<=size*size;k++)
		   {
			   try {
				Thread.sleep(700);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} 
			   move_x[1]+=move_x[k];
			   move_y[1]+=move_y[k];
			   System.out.println("*********************************************************************图  "+k+"**********************************************************************"); 
			   for(int i=0;i<size;i++)
			   {
				   for(int j=0;j<size;j++)
				   {			  
					   if(((i==move_x[1])&&(j==move_y[1]))||(mapRecord[i][j]==1))
					   {	
						   if(mapRecord[i][j]==1)
							   System.out.print("#  ");
						   else
						   {
							   System.out.print("$  ");
							   mapRecord[i][j]=1;
						   }
					   }
					   else
						   System.out.print("!  "); 
				   }
				   System.out.println();
			   }
		   }		   
	   }
	   public static void main(String arg[])
		{
			Scanner scanner =new Scanner(System.in);
			int size=0;
			System.out.println("请输入n×n棋盘大小，8×8和44×44之间,偶数的偶数：");
			try
			{
				size=scanner.nextInt();
				while(size>44||size<8||(size%2!=0))
				{
					System.out.println("输入应在8×8和44×44之间的偶数,请重新输入：");
					size=scanner.nextInt();
				}	
				System.out.println("起始点row位置：");
				int row=0;
					row=scanner.nextInt();
				if(row>=size||row<0)
				{
					System.out.println("位置超出棋盘界限，row设为 "+size/2);
					row=size/2;
				}	
				System.out.println("起始点column位置：");
				int column=0;
					column=scanner.nextInt();
				if(column>=size||column<0)
				{
					System.out.println("位置超出棋盘界限，column设为 "+size/2);
					column=size/2;
				}	
				Knight knight=new Knight(row,column,size);	
				knight.search();
			}
			catch(InputMismatchException e)
			{System.out.println("你输入的不是正整数 "+e.toString());}
		}
}