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);
}
}