Ashish Musani
BAN USERSolution written in Java
This is for only one test case. You can modify it for multiple test cases.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Point
{
int xCord;
int yCord;
public Point(int x, int y)
{
this.xCord = x;
this.yCord = y;
}
}
class Ideone
{
static int startX;
static int startY;
static int endX;
static int endY;
static int adjMatrix[][];
static int arr[] ;
static int minDist = Integer.MAX_VALUE;
static int N;
static void calculateDistance(int a[])
{
int dist = 0;
int size = a.length;
dist = adjMatrix[0][a[0]];
for(int i=1; i<N; i++)
{
dist += adjMatrix[a[i]][a[i-1]];
}
dist += adjMatrix[a[N-1]][N+1];
if(dist<minDist)
minDist = dist;
}
static void findMinPath(int a[], int l, int r)
{
if(l==r)
{
calculateDistance(a);
}
else
{
for(int i=l; i<=r; i++)
{
a = swap(a, l, i);
findMinPath(a, l+1, r);
a = swap(a, l, i);
}
}
}
static int[] swap(int a[], int x, int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
return a;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
N = in.nextInt();
startX = in.nextInt();
startY = in.nextInt();
endX = in.nextInt();
endY = in.nextInt();
Point pts[] = new Point[N+2];
pts[0] = new Point(startX, startY);
pts[N+1] = new Point(endX, endY);
for(int i=1; i<N+1; i++)
{
int xLoc = in.nextInt();
int yLoc = in.nextInt();
pts[i] = new Point(xLoc, yLoc);
}
adjMatrix = new int[N+2][N+2];
for(int x=0; x<N+2; x++)
{
for(int y=0; y<N+2; y++)
{
adjMatrix[x][y] = Math.abs(pts[x].xCord-pts[y].xCord) + Math.abs(pts[x].yCord-pts[y].yCord);
adjMatrix[y][x] = adjMatrix[x][y];
}
}
arr = new int[N];
for(int count=0; count<N; count++)
{
arr[count] = count+1;
}
findMinPath(arr, 0, N-1);
System.out.println(minDist);
}
}
Can anyone provide a correct approach to solve this question?
- Ashish Musani April 17, 2018