posts - 195,  comments - 30,  trackbacks - 0
package BotClean;

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution2 {

    static class Status{
        int id;//current city
        String action;
        int distance;
        Vector<Integer> unvisited;
        HashSet<Integer> visited;
        public Status(int id)
        {
            this.id=id;
        }
    }


    static class DirtyDot{
        int id;//current city
        int x;
        int y;
        
        public DirtyDot(int id, int x, int y)
        {
            this.id=id;
            this.x=x;
            this.y=y;
        }
    }
/* Head ends here */
    static void next_move(int x, int y, String[] board){
        TSP(board,x,y);
                               
    }

/* Tail starts here */
    public static void main(String[] args) {
        //TSP(null,0,0);
        
        Scanner in = new Scanner(System.in);
        int [] pos = new int[2];
        String board[] = new String[5];
        for(int i=0;i<2;i++) pos[i] = in.nextInt();
        for(int i=0;i<5;i++) board[i] = in.next();
        System.out.println("begin now!");
        next_move(pos[0], pos[1], board);
    }
    

    
    public static void TSP(String[] board, int x, int y) {
        
        String dirty="d";
        HashMap<Integer, DirtyDot> dirtyList=new HashMap<Integer,DirtyDot>();
        int id=1;
        DirtyDot tempDirtyDot2;
        DirtyDot tempDirtyDot=new DirtyDot(id-1,x,y);
        dirtyList.put(id,tempDirtyDot);
        
        for(int i=0;i<board.length;i++)
        {
            if(board[i].contains(dirty))
            {
                int position;
                position=board[i].indexOf(dirty, 0);
                while(position!=-1)
                {
                    tempDirtyDot=new DirtyDot(id,i,position);
                    dirtyList.put(id,tempDirtyDot);                   
                    id++;
                    position=board[i].indexOf(dirty,position+1);
                    System.out.println("position"+position);
                }
            }
        }
        
//        int MAX=id;
//        int dist[][]=new int[MAX][MAX];
//        
//        for(int i=0;i<MAX;i++)
//            for(int j=0;j<MAX;j++)
//               {
//                tempDirtyDot=dirtyList.get(i);
//                tempDirtyDot2=dirtyList.get(j);
//                 dist[i][j]=Math.abs(tempDirtyDot.x-tempDirtyDot2.x)+Math.abs(tempDirtyDot.y-tempDirtyDot2.y);
//               }
        
          int MAX=4;
        
          int dist[][]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; 
        
        Vector<Status> currentStatus=new Vector<Status>();
        Vector<Status> previousStatus;
        /*Initialize current Status Vector*/
        for(int i=1;i<MAX;i++)
        {
            Status status=new Status(i);
            status.distance=dist[i][0];
            status.unvisited=new Vector<Integer>();
            status.visited=new HashSet<Integer>();
            currentStatus.add(status);
        }
        System.out.println("Initialized current Status Vector");
        //System.out.println(currentStatus.size());
        
        for(int j=0;j<MAX-2;j++)
        {
            previousStatus=currentStatus;
            currentStatus=new  Vector<Status>();
            //System.out.println(previousStatus.size());
            for(int i=1;i<MAX;i++)// enumerate each node
            {
                for(int k=0;k<previousStatus.size();k++)
                {
                    Status tempStatus=previousStatus.elementAt(k);
                    if(isContain(tempStatus,i)==false)//gurantee node i is not in tempStatus
                    {
                        Status newStatus=new Status(i);
                        newStatus.distance=tempStatus.distance+dist[i][tempStatus.id];
                        System.out.println("id"+tempStatus.id);
                        newStatus.visited=new HashSet<Integer>(tempStatus.visited);
                        newStatus.unvisited=new Vector<Integer>(tempStatus.unvisited);
                        newStatus.unvisited.add(0,(Integer)(tempStatus.id));
                        newStatus.visited.add(tempStatus.id);
                        currentStatus.add(newStatus);
                        System.out.println(newStatus.unvisited.size());
                        System.out.println(newStatus.distance);
                        
                    }
                }
            }
            //System.out.println(currentStatus.size());
            currentStatus=optimize(currentStatus);//dp process  
            
//System.out.println(currentStatus.size());
        }//end for
        
        Iterator<Status> iterator = currentStatus.iterator();  
   
        Status tempStatus=iterator.next();
        Status shortest=tempStatus;
        int minDistance=dist[0][tempStatus.id]+tempStatus.distance;
        System.out.println("1:"+tempStatus.distance);
        System.out.println("2:"+dist[0][tempStatus.id]);
        
        while (iterator.hasNext()) {  
             tempStatus=iterator.next();  
             int tempDistant=dist[0][tempStatus.id]+tempStatus.distance;
             System.out.println("11:"+tempStatus.distance);
             System.out.println("22:"+dist[0][tempStatus.id]);
             System.out.println("33:"+tempStatus.id);
             
             if(tempDistant<minDistance)
             {
                 minDistance=tempDistant;
                 System.out.println("in loop"+minDistance);
                 //System.out.println(tempStatus.distance);
                 shortest=tempStatus;
             }
          }
        
        System.out.println("distance: "+minDistance);
        System.out.println("size:"+shortest.unvisited.size());
        System.out.print(" 1");
        System.out.print(" "+shortest.id);
        for(int i=0;i<shortest.unvisited.size();i++)
            {
                 int tmp=shortest.unvisited.get(i)+1;
               System.out.print(" "+tmp);
            }
        System.out.println(" 1");
    }
    
    private static Vector<Status> optimize(Vector<Status> cs) {
        Status tempStatus,anotherStatus;
        int j;

        Iterator<Status> iterator = cs.iterator();    
         while (iterator.hasNext()) {  
             tempStatus=iterator.next();  
              for(j=0;j<cs.size();j++)
                {
                      anotherStatus=cs.get(j);
                      if(tempStatus.id==anotherStatus.id&&tempStatus.visited.equals(anotherStatus.visited))
                      {
                          if(tempStatus.distance>anotherStatus.distance)
                          {
                              iterator.remove();
                             break;
                          }
                      }
                }
             
         }    
          return cs;
    
    }

    static boolean isContain(Status sta, int i)
    {
        if(i==sta.id)
            return true;
        else
          return sta.unvisited.contains(i);
     }
    

}

posted on 2013-03-31 14:39 luis 阅读(980) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2013年3月>
242526272812
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜