Short Time

Reach from (x,y) points to (x1,y1) points. There are two ways in which you can travel.

Option 1 is jumping: if you are at (x,y), you can jump to one of the four neighboring grid points: (x+1,y), (x-1,y), (x,y+1), or (x,y-1). Each jump takes one second.

Option 2 is using a port. There are three ports. Each of them connects two different grid points. If you are at one of the endpoints, you may activate the port and travel to its other endpoint. Traveling by port takes 10 seconds.

Find out the the shortest time in which you can reach (x1,y1) points.

Method: public int shortestTime(int x, int y, int x1, int y1, String[] ports)

Examples

1)i/p=>3 3 4 5, {“1000 1001 1000 1002”, “1000 1003 1000 1004”, “1000 1005 1000 1006”}  Returns: 3
Steps are
(3,3) to (3,4) = 1 second
(3,4) to (3,5) = 2 second
(3,5) to (4,5) = 3 second

2)i/p=>0 0 20 20, {“1 1 18 20”, “1000 1003 1000 1004”, “1000 1005 1000 1006”}  Returns: 14
Steps are
(0,0) to (0,1) = 1 second
(0,1) to (1,1) = 2 second
(1,1) to (18,1) = 10 second (used port)
(18,1) to (18,20) = 10 second (used port)

3)i/p=>0 0 20 20 {“1000 1003 1000 1004”, “18 20 1 1”, “1000 1005 1000 1006”} Returns: 14
Same the above steps, but the ports may be used in either direction, and in any order.

4)i/p=>10 10 10000 20000, {“1000 1003 1000 1004”, “3 3 10004 20002”, “1000 1005 1000 1006”} Returns: 30
Steps are
(10,10) to (3,3) = (10-3)7+(10-3)7 = 14 seconds
(3,3) to (10004 20002) = 10+10 = 20 seconds (used port)
(10004 20002) to (10000 20000) = (10004-4)4+(20000-2)2 = 6 seconds

5)i/p=>3 7 10000 30000, {“3 10 5200 4900”, “12212 8699 9999 30011”, “12200 8701 5203 4845”} Returns: 117
Steps are
(3,7) to (3,10) = 3 seconds
(5200,4900) to (5203,4845) = 10+3+55 = 68 seconds (used port)
(12200,8701) to (12212,8699) = 10+12+2 = 24 seconds (used port)
(9999,30011) to (10000,30000) = 10+1+11 = 22 seconds (used port)

6)i/p=>0 0 1000000000 1000000000, {“0 1 0 999999999”, “1 1000000000 999999999 0”, “1000000000 1 1000000000 999999999”}  Returns: 36
Steps are
(0 ,0) to (0, 1) = 1 second
(0, 999999999) to (1, 1000000000) = 10 +1+1= 12 seconds (used port)
(999999999 0) to (1000000000 1) = 10 +1+1= 12 seconds (used port)
(1000000000 999999999) to (1000000000 1) = 10 + 1= 11 seconds (used port)

public class ThreeTeleports{

    public     int shortestDistance(int xMe, int yMe, int xHome, int yHome, String[] teleports) {
        int shortdistance  = 0;

        long telvalue[]= new  long [16];
        long tpoint[][]= new  long [8][8];
        int count = 0;
        telvalue[count++] = xMe;
        telvalue[count++] = yMe;
        telvalue[count++] = xHome;
        telvalue[count++] = yHome;
        for (int i =0 ;i<teleports.length;i++) {
            String[] teleport = (teleports[i]).split(" ");
            telvalue[count++] = Integer.parseInt(teleport[0]);
            telvalue[count++] = Integer.parseInt(teleport[1]);
            telvalue[count++] = Integer.parseInt(teleport[2]);
            telvalue[count++] = Integer.parseInt(teleport[3]);
        }
        int icount = 0,i=0;
        while (icount<=15) {
            int jcount= 0,j=0;
            long x = telvalue[icount], y = telvalue[icount+1];
            while (jcount<=15) {
                long x1 = telvalue[jcount], y1 = telvalue[jcount+1];
                if (tpoint[i][j]!=10)
                    tpoint[i][j] = Math.abs(x-x1) + Math.abs(y-y1);
                if(i>=2 && i%2==0)
                    tpoint[i][i+1] = tpoint[i+1][i] = 10;
                j++;
                jcount+=2;
            }
            i++;
            icount+=2;
        }

        for (int k =0 ;k<8;k++)
            for (i =0 ;i<8;i++)
                for (int j =0 ;j<8;j++)
                    tpoint[i][j] = Math.min(tpoint[i][j],tpoint[j][k]+ tpoint[k][i]);

        shortdistance = (int)tpoint[0][1];
        System.out.println(shortdistance);
        return shortdistance;
    }



    public static void main(String[] args) {
        ThreeTeleports tt= new ThreeTeleports();
        tt.shortestDistance(3,3,4,5, new String[] {"1000 1001 1000 1002", "1000 1003 1000 1004", "1000 1005 1000 1006"});

        tt.shortestDistance(0,0,20,20, new String[] {"1 1 18 20", "1000 1003 1000 1004", "1000 1005 1000 1006"});

        tt.shortestDistance(0,0,20,20, new String[] {"1000 1003 1000 1004", "18 20 1 1", "1000 1005 1000 1006"});

        tt.shortestDistance(10,10,10000, 20000, new String[] {"1000 1003 1000 1004", "3 3 10004 20002", "1000 1005 1000 1006"});

        tt.shortestDistance(3,7,10000, 30000, new String[] {"3 10 5200 4900", "12212 8699 9999 30011", "12200 8701 5203 4845"});

        tt.shortestDistance(0,0,1000000000, 1000000000, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
        
        tt.shortestDistance(3, 3, 4, 5, new String[] {"1000 1001 1000 1002", "1000 1003 1000 1004", "1000 1005 1000 1006"});
        
        tt.shortestDistance(0, 0, 20, 20, new String[] {"1 1 18 20", "1000 1003 1000 1004", "1000 1005 1000 1006"});
        
        tt.shortestDistance(0, 0, 20, 20, new String[] {"1000 1003 1000 1004", "18 20 1 1", "1000 1005 1000 1006"});
        
        tt.shortestDistance(10, 10, 10000, 20000, new String[] {"1000 1003 1000 1004", "3 3 10004 20002", "1000 1005 1000 1006"});
        
        tt.shortestDistance(3, 7, 10000, 30000, new String[] {"3 10 5200 4900", "12212 8699 9999 30011", "12200 8701 5203 4845"});
        
        tt.shortestDistance(0, 0, 1000000000, 1000000000, new String[] {"1 1 2 2", "3 3 4 4", "5 5 6 6"});
        
        tt.shortestDistance(0, 1000000000, 1000000000, 0, new String[] {"1 1 2 2", "3 3 4 4", "5 5 6 6"});
        
        tt.shortestDistance(0, 0, 1000000000, 1000000000, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
        
        tt.shortestDistance(7, 2, 999999991, 4, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
        
        tt.shortestDistance(10, 500000000, 1000000000, 1000000000, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
        
        tt.shortestDistance(100000000, 500000000, 900000000, 500000000, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
        
        tt.shortestDistance(100000000, 100000000, 900000000, 900000000, new String[] {"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"});
    }
}

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: