hw3.java

其中readme是整个程序的要求

import  java.io.*;
import  java.util.*;


public class hw3 {
     static      String s = "";
     static      int c[][]=new int[200000][14];
	 //0--8表示的是这个节点中的状态,9表示深度,10表示前趋,11表示(U=1,L=2,R=3,D=4),12表示f（n），13表示0的位置 
     static     int countex=0; //已经扩展的节点数目 
     static     int lp=0;//当前正要扩展的节点所在的位置
	 static     int rp=0;//现在已经得到的节点数目 
     static     int pop[]={1,2,3,8,0,4,7,6,5}; //终结状态
     
  public static boolean ok()    //判断是否有解
	{
	   int k=0;
	   for (int i=0;i<9;i++)
	   {
		    for (int j=i+1;j<9;j++ )
		    {
				if ((c[lp][i]>c[lp][j]) && (c[lp][j]!=0))
				{
					k++;
				}
		    }
	   }
      if (k%2==0)
      {
		  return false;
      }
	  else return true;
    }

   public static int manhaton()     //求出h（n）（即 mahatton distance）

	{
	    int k=0;
		for (int i=0;i<9 ;i++ )
		{
		    if (c[rp][i]==0)
		    {  
                c[rp][13]=i;
		    }
          if (c[rp][i]==1)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-1)+Math.abs(l-1);
		    }
          if (c[rp][i]==2)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-1)+Math.abs(l-2);
		    }
			if (c[rp][i]==3)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-1)+Math.abs(l-3);
		    }
			if (c[rp][i]==4)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-2)+Math.abs(l-3);
		    }
            if (c[rp][i]==5)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-3)+Math.abs(l-3);
		    }
			if (c[rp][i]==6)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-3)+Math.abs(l-2);
		    }
			if (c[rp][i]==7)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-3)+Math.abs(l-1);
		    }
			if (c[rp][i]==8)
		    {  
               int m,l;
			   m=i/3+1;
			   l=i%3+1;
			   k=k+Math.abs(m-2)+Math.abs(l-1);
		    }
		}  
		return k;
    }
   public static boolean issolution()   //判断当前要扩展的节点lp是不是解 
	{
	   boolean is=true;
	   for (int i=0;i<9 ;i++ )
	   {
         if (pop[i]!=c[lp][i])
         {
			 is=false;
         }
	   }
      return is;
	}
   public static void out()   //输出结果
	{
	   System.out.println("解的长度为:"+(c[lp][9]));
	   String ss="";
	   int k=lp;
	   for (int i=c[lp][9];i>0;i-- )
	   {
          if (c[k][11]==1)
          {
			  ss='U'+ss;
          }
		  if (c[k][11]==2)
          {
			  ss='L'+ss;
          }
		  if (c[k][11]==3)
          {
			  ss='R'+ss;
          }
		  if (c[k][11]==4)
          {
			  ss='D'+ss;
          }
         k=c[k][10]; 
	   }
      System.out.println(ss);
      System.out.println("扩展结点数目为:"+countex);

	}
   public static boolean again()  //判断新生成的节点rp是不是已经生成过了
	{
	    for (int i=0;i<rp;i++)
	    {
			boolean fanfu=true;
			 for (int k=0;k<9 ;k++ )
			 {
				 if (c[rp][k]!=c[i][k])
				 {
					 fanfu=false;
				 }
			 }
          if (fanfu)
          {
			  return true;
          }
	    }
      return false;
	}
  public static void charu()   //判断出新的节点后将其插入尚未扩展的队列中
	{   int i=rp;

		while ((i>lp+1) && (c[rp][12]<=c[i-1][12]))
		{
			i=i-1;
		}
        int temp[] = new int[14];
       for (int k=0;k<=13 ;k++ )
       {
		   temp[k]=c[rp][k];
       }
    for (int k=rp;k>i;k-- )
    {
		for (int j=0;j<=13 ;j++ )
		{
			c[k][j]=c[k-1][j];
		}
    }
     for (int k=0;k<=13 ;k++ )
     {
		 c[i][k]=temp[k];
     }
  }

   public static void qiujie()   //求解的过程
	{
	   boolean nosolution=true;  //是否有解了
	  
	   while ((lp<=rp) && nosolution)
	   {
          if (issolution())
          {
			  nosolution=false;
		      out();  
          }
         else 
		   {  countex++;   //扩展节点数目+1
		      int m,l,x,y;
			  m=c[lp][13]/3+1;
			  l=c[lp][13]%3+1;
              x=m-1;y=l;  //DOWN的扩展
			  if (x>0)
			  {   rp++;
				  for (int temp=0;temp<9 ;temp++ )
				  { 
					 c[rp][temp]=c[lp][temp];  
				  }
                  c[rp][(x-1)*3+y-1]=c[lp][(m-1)*3+l-1];
				  c[rp][(m-1)*3+l-1]=c[lp][(x-1)*3+y-1];
				  c[rp][9]=c[lp][9]+1;
				  c[rp][10]=lp;
				  c[rp][11]=4;
				  c[rp][12]=c[rp][9]+manhaton();
				  c[rp][13]=(x-1)*3+y-1;
				  if (c[rp][11]+c[lp][11]!=5)
				  {
					  if (again()) rp=rp-1;  else  charu();
				  }
				  else rp=rp-1;
			  }
			  m=c[lp][13]/3+1;
			  l=c[lp][13]%3+1;
              x=m+1;y=l; //UP的扩展
			  if (x<=3)
			  {   rp++;
				  for (int temp=0;temp<9 ;temp++ )
				  { 
					 c[rp][temp]=c[lp][temp];  
				  }
                  c[rp][(x-1)*3+y-1]=c[lp][(m-1)*3+l-1];
				  c[rp][(m-1)*3+l-1]=c[lp][(x-1)*3+y-1];
				  c[rp][9]=c[lp][9]+1;
				  c[rp][10]=lp;
				  c[rp][11]=1;
				  c[rp][12]=c[rp][9]+manhaton();
				  c[rp][13]=(x-1)*3+y-1;
				  if (c[rp][11]+c[lp][11]!=5)
				  {
					  if (again()) rp=rp-1;  else  charu();
				  }
				  else rp=rp-1;
			  }
			  m=c[lp][13]/3+1;
			  l=c[lp][13]%3+1;
              x=m;y=l-1;  //RIGHT的扩展
			  if (y>0)
			  {   rp++;
				  for (int temp=0;temp<9 ;temp++ )
				  { 
					 c[rp][temp]=c[lp][temp];  
				  }
                  c[rp][(x-1)*3+y-1]=c[lp][(m-1)*3+l-1];
				  c[rp][(m-1)*3+l-1]=c[lp][(x-1)*3+y-1];
				  c[rp][9]=c[lp][9]+1;
				  c[rp][10]=lp;
				  c[rp][11]=3;
				  c[rp][12]=c[rp][9]+manhaton();
				  c[rp][13]=(x-1)*3+y-1;
				  if (c[rp][11]+c[lp][11]!=5)
				  {
					  if (again()) rp=rp-1;  else  charu();
				  }
				  else rp=rp-1;
			  }
			  m=c[lp][13]/3+1;
			  l=c[lp][13]%3+1;
              x=m;y=l+1;     //LEFT的扩展
			  if (y<=3)
			  {   rp++;
				  for (int temp=0;temp<9 ;temp++ )
				  { 
					 c[rp][temp]=c[lp][temp];  
				  }
                  c[rp][(x-1)*3+y-1]=c[lp][(m-1)*3+l-1];
				  c[rp][(m-1)*3+l-1]=c[lp][(x-1)*3+y-1];
				  c[rp][9]=c[lp][9]+1;
				  c[rp][10]=lp;
				  c[rp][11]=2;
				  c[rp][12]=c[rp][9]+manhaton();
				  c[rp][13]=(x-1)*3+y-1;
				  if (c[rp][11]+c[lp][11]!=5)
				  {
					  if (again()) rp=rp-1;  else  charu();
				  }
				  else rp=rp-1;

			  }
		   }

        lp=lp+1;  //扩展完一个节点以后,准备进行下一个节点的扩展
	   }
	}

  public static void main(String []args) 
 {   
         try
         {
          BufferedReader in = new BufferedReader( new FileReader (args[0]));
          s= in.readLine();   //从文件中读出表示初始状态的字符串
          in.close();
         }
         catch(Exception e )
         {
                 System.out.println("文件有问题或者文件不存在!!!");  
         }
		  System.out.println("初始状态是:"+s);
         int j=0;     
         for (int i=0;i<s.length();i++)
           {
            if (s.charAt(i)!=' ')
            {
               c[0][j]=Character.getNumericValue(s.charAt(i));
			   j++;
            }
        }   
		//从字符串中得到初始状态的数字数组
   c[0][9]=0;c[0][10]=-1;c[0][11]=0;c[0][12]=c[0][9]+manhaton();
 if (!ok())
 { 
	 System.out.println("这个状态无解!!!");
 }
else  qiujie();

}


}