pictrue.java

该程序实现公园导游功能

//import java.awt.*;
//import javax.swing.*
class Pictrue{
	int weight[][]=new int[15][15];   //path between landscape;
	int entrance;
	int exit;
	int Max=Integer.MAX_VALUE;
	public Pictrue()
	{   entrance=0;
      	exit=0;
      	weight[0][1]=150;  weight[1][7]=165;  weight[7][8]=220;
      	weight[8][9]=125;  weight[9][10]=170; weight[10][11]=105;
      	weight[10][12]=110; weight[12][13]=225; weight[0][2]=125;
      	weight[2][11]=10;  weight[2][12]=235; weight[2][3]=195;
      	weight[3][4]=170;  weight[4][5]=165;  weight[5][6]=95;
      	weight[6][13]=135;weight[3][14]=100;
      	for(int i=0;i<15;i++)
      		for(int j=i;j<15;j++)
      			if(weight[i][j]!=0&&j!=i)
      				weight[j][i]=weight[i][j];
      			else
      				weight[i][j]=weight[j][i]=Max;
    	   
	
	}
	public AllPath findpath(int from,int to)
	{   
	    if(from==to)
	      return null;
	                               
	    Path path=new Path();
	    path.insert(new Node(from,null));
	    AllPath allpath=new AllPath();   //to store all paths
	    allpath.insert(path);
	    int[] isvisited=new int[15];
	    isvisited[from]=-1;
        boolean success[]={false,false};
        Dfs(from,to,0,isvisited,path,allpath,success);
        return allpath;
     }
     public AllPath findallpath()
     {
     	Path path=new Path();
     	path.insert(new Node(0,null));
     	AllPath allpath=new AllPath();
     	allpath.insert(path);
     	int[] isvisited=new int[15];
     	isvisited[0]=-1;
     	boolean success[]={false,false};
     	findhole(0,1,0,isvisited,path,allpath,success);
     	return allpath;
     }
     public Path getbestpath(AllPath allpath)
     {
     	Path path,temp;
     	path=temp=allpath.firstPath;
     	Node node=path.head;    
     	if(path.nextPath==null)
     	  return path;
  
     	temp=temp.nextPath;
     	while(temp!=null)
     	{
     	  if(temp.length>path.length)
     	    path=temp;
     	  temp=temp.nextPath; 
     	}
     	return path;
     }
    
    private void Dfs(int from,int to,int nowcost,int[] isvisited,Path path,AllPath allpath,boolean[] success)
    {  
       for(int i=0;i<15;i++)
       {  
          if(weight[from][i]<Max&&isvisited[i]!=-1&&nowcost+weight[from][i]<=allpath.leastcost)
           {  
              isvisited[i]=-1;
              Path newpath;
              if(success[0])
              {  
              	 newpath=new Path();          //clone the path till this node;
                 newpath=path.myclone(from);
                 Node node=newpath.head;
              }
              else 
              {  newpath=path;            //some node in path maybe illegal,discard
                 
                 if(newpath.presentNode.point!=from)
                 { 
                 	Node node=path.head;
                   path.length=0;
                   while(node!=null)
                   {  path.length++;
                 	if(node.point==from)
                 	 {  node.next=null;  break;}
                 	    node=node.next;
                   }
                  path.presentNode=node;
                 }
               }
              
              newpath.insert(new Node(i,null));
    	      if(i==to)
    	      {  
    	        if(allpath.leastcost>nowcost+weight[from][i])
    	          {
    	          	allpath.leastcost=nowcost+weight[from][i];
    	          	allpath.firstPath=null;                       //find a path shorter than previos,discard all;       
    	          }    	         
    	          allpath.insert(newpath);             //add this path;
    	          success[0]=true;  
                isvisited[i]=0;
               }
              else 
              { 
                Dfs(i,to,nowcost+weight[from][i],isvisited,newpath,allpath,success);
                isvisited[i]=0;
              }
            }
      } 
    } 
     private void findhole(int from,int length,int nowcost,int[] isvisited,Path path,AllPath allpath,boolean[] success)
    {  
       for(int i=0;i<15;i++)
       {  
          if(weight[from][i]<Max&&isvisited[i]!=-1&&nowcost+weight[from][i]<=allpath.leastcost)
           {  
         
              isvisited[i]=-1;
              Path newpath;
              if(success[0])
              {  
              	 newpath=new Path();          //clone the path till this node;
                 newpath=path.myclone(from);
                 Node node=newpath.head;
              }
              else 
              {  newpath=path;            //some node in path maybe illegal,discard
                 
                 if(newpath.presentNode.point!=from)
                 { 
                 	Node node=path.head;
                   path.length=0;
                   while(node!=null)
                   {  path.length++;
                 	if(node.point==from)
                 	 {  node.next=null;  break;}
                 	    node=node.next;
                   }
                  path.presentNode=node;
                 }
               }
              
              newpath.insert(new Node(i,null));
    	      if(i==14&&length==14)
    	      {  
    	        if(allpath.leastcost>nowcost+weight[from][i])
    	          {
    	          	allpath.leastcost=nowcost+weight[from][i];
    	          	allpath.firstPath=null;                       //find a path shorter than previos,discard all;       
    	          }    	         
    	          
    	          allpath.insert(newpath);             //add this path;
    	          success[0]=true;  
                  isvisited[i]=0;
               }
              else if(i!=14) 
              { 
                findhole(i,length+1,nowcost+weight[from][i],isvisited,newpath,allpath,success);
                isvisited[i]=0;
              }
              else
               isvisited[i]=0;
            }
      } 
    }               	          
}
class AllPath{
   Path firstPath;
   Path presentPath;
   int leastcost;
  public AllPath()
  {
  	leastcost=Integer.MAX_VALUE;
  }
  public AllPath(Path firstPath)
  {
  	this.firstPath=firstPath;
  	this.presentPath=firstPath;
  	
  }	
  public void insert(Path path)
  {
  	if(firstPath==null)
  	 {   firstPath=path;
  	     presentPath=path;
     }
    else
    {
      presentPath.nextPath=path;
      presentPath=path;
    }
  }
}
class Path
{
	Node head;
	Node presentNode;
    Path nextPath;
	int length;
	public Path()
	{
		length=0;
		head=null;
	}
	public void insert(Node node)
	{
		length++;
		if(this.head==null)
		{	this.head=node;
            presentNode=node;
		}
		else
		{
		 presentNode.next=node;
		 presentNode=node;
		}
	}
	public Node getHead()
	{
		return head;
	}
	public Node getPresent()
	{
		return presentNode;
	}
	public Path myclone(int index)
	{
		Path newpath=new Path();
		Node newhead=head;
		while(true)
          if(newhead!=null)
          {   newpath.insert(new Node(newhead.point,null));
              if(newhead.point==index)
                break;
              newhead=newhead.next;
          } 
         return newpath;    
	}	
  
}
class Node
{
	public int  point;
	public Node next;
	public void setNext(Node node)
	{
		next=node;
	}
	public Node(int point,Node next)
	{
		this.point=point;
		this.next=next;
	}
	
}