Samsung Interview Question Software Engineers
Country: India
Solution 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);
}
}
I can't believe my bad luck :( !! I saw this problem but didn't care to solve it...and the exact same problem popped up in my exam!
///////////////////////////////////////////////////////////////
// Author - Prakhar Pratyush
// IIT Roorkee, Final Year
// er.prakhar2b@gmail.com
//
////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
int dp[12][1 << 11]; // bitmask with max 11 bits
int x[12], y[12]; // 5<= N <= 10 , home, office
int n;
int calc(int p, int mask) {
if(p == 0 && mask == 0) return 0; // Base case - reached home and visited all customers
else if(p == 0) return 1e9;
// When recursion hits base case (home + all traversed), to eliminate other base
// case (home + not all traversed), we need to return higher value -- thus 1e9
dp[p][mask]=1e9;
for (int i = n; i >=0 ; --i) {
if (mask & (1 << i)) { // Check if ith bit is 1
int dist = abs(x[p] - x[i]) + abs(y[p] - y[i]);
dp[p][mask] = min( dp[p][mask], calc(i, mask ^ (1 << i)) + dist); // toggle the ith bit to indicate this bit as visited
}
}
return dp[p][mask];
}
int main() {
std::ios::sync_with_stdio(false);
for (int i = 1; i <= 10; ++i) {
cin>>n;
cin>>x[0]>>y[0];
cin>>x[n+1]>>y[n+1];
for (int j = 1; j <= n; ++j) {
cin>>x[j]>>y[j];
}
memset(dp, -1, sizeof dp);
int mask = (1 << (n + 1)) - 1; // n+1 bits representing n customers and office- starting point
cout<<"Case #"<< i <<": "<< calc(n + 1, mask); // Sending end point- home
}
return 0;
}
/* Proof Of Concept------------------------------------------------------------------------------
calc(n+1, 1111............1) // destination , initially all bit is 1- means not visited
/ \
min of | calc(n,0111.......1) calc(n-1,10111....1) .... calc(0,11......0)
/ \
min of | calc(n-1, 0011....1) ... // If ith bit is not 1, recursive call won't take place
.
.
.
/
min of | calc(0, 0000....0) ...
*/
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <stdio.h>
#define MAXIMUM 10000000
using namespace std;
int calculate_distance(pair<int, int> a, pair<int, int> b){
int maxX = max(a.first, b.first);
int minX = min(a.first, b.first);
int maxY = max(a.second, b.second);
int minY = min(a.second, b.second);
return (maxX - minX + maxY - minY);
}
void print(int x){
cout<<x<<" ";
}
int main(){
int no_neighbour;
cin>>no_neighbour;
vector< pair<int, int> > coords;
pair<int, int> temp;
vector<int> nodes;
int mat[no_neighbour+2][no_neighbour+2];
for(int i=0; i<no_neighbour+2; i++){
cin>>temp.first>>temp.second;
coords.push_back(temp);
}
for(int i=0; i<no_neighbour+2; i++){
for(int j=0; j<no_neighbour+2; j++){
mat[i][j] = calculate_distance(coords[i],coords[j]);
// printf("%4d", mat[i][j]);
}
if(i!=0 && i!=1)nodes.push_back(i);
cout<<endl;
}
int mindistance = MAXIMUM;
do{
// for_each(nodes.begin(), nodes.end(), print);
int distance = 0;
int prev = 1;
for(int i=0; i<no_neighbour; i++){
distance+=mat[prev][nodes[i]];
prev = nodes[i];
}
distance += mat[prev][0];
// cout<<distance<<endl;
if(distance < mindistance) mindistance = distance;
}while(next_permutation(nodes.begin(), nodes.end()));
cout<<mindistance<<endl;
return 0;
}
I guess answer for the third case should be 352 not 368. I am certain because I have checked for all the possible combination. You can verify this by my code.
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/* <Program description>
*
* Mr. Kim has to deliver samples to N costumer.
* Find the shortest way to deliver it and return his home
*
* Mr.Kim<Office>--> Costumer1-->....CustomerN--> His Home.
*
*
*
*/
/* <Idea --> Solution>
*
* find all possible path:
* There is N!-1 possible path
*
* for : earch path from 1----> N!-1
* (i)--> Corresponding sequence --> {Permuation}
* --> determine Shortest distance and print "the path sequence"
*
*/
/* <Result >
*
* Case #1: 200: path -> Office->[2-1-4-0-3]-->Home
* Case #2: 304: path-> Office->[1-3-5-0-4-2]-->Home
* Case #3: 366: path-> Office->[6-3-9-4-8-0-5-1-7-2]-->Home
*/
namespace ShortestPathDelivery
{
class Program
{
static void Main(string[] args)
{
// Test case:
// Case 1:
/*
const int N = 5;
int[,] xyLocation = {{ 70, 40 }, { 30, 10 }, { 10, 5 }, { 90, 70 }, { 50, 20 }};
int[,] xyOffice = { {0,0}};
int[,] xyHome = { { 100, 100 } };
*
*/
//case 2:
/*
const int N = 6;
int[,] xyLocation = { { 19, 22 }, { 31, 15 }, { 27, 29 }, { 30, 10 }, { 20, 26 },{5,14} };
int[,] xyOffice = { { 81, 88} };
int[,] xyHome = { { 85, 80 } };
*/
const int N = 10;
int[,] xyLocation = { {35,93 }, { 62,64 }, { 96,39}, { 36,36 }, { 5,59 },
{59,96},{61,7},{64,43},{43,58},{1,36} };
int[,] xyOffice = { {39,9}};
int[,] xyHome = { { 97, 61 } };
int[] pathseq = new int[N];
int[] finalPath = new int[N];
int[] shortestPath = new int[N];
double dis_Min = 10000 ;
// pathseq = GetPathsequence(2982, N);
//List allpath
for (int i = 0; i < GetNmul(N); i++)
{
pathseq = GetPathsequence(i, N);
// PrintPath(pathseq);
finalPath = Convertsequence(pathseq);
// PrintPath(finalPath);
// Calculate corresponding distance
double tempDis = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
// System.Console.Write(" --Dis: {0} ", CalDistance(finalPath, xyLocation, xyHome, xyOffice));
if (i == 0)
{
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
else
{
if (dis_Min > CalDistance(finalPath, xyLocation, xyHome, xyOffice))
{
shortestPath = finalPath;
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
}
}
PrintPath(shortestPath);
System.Console.WriteLine(" Shortest Dis: {0} ", dis_Min);
System.Console.ReadKey();
}
// This function return the sequence from n--> factorized sequence.
public static int[] GetPathsequence(int n, int Ncustom)
{
int[] aSequence = new int[Ncustom];
int divide = 0;
int remainder = 0;
for (int i = Ncustom-1; i >=0;i-- )
{
if(i==Ncustom-1)
{
divide = (int)n / GetNmul(Ncustom-1);
remainder = (int)n % GetNmul(Ncustom-1);
aSequence[Ncustom-1-i] = divide;
}
else
{
divide = remainder / GetNmul(i);
remainder = remainder % GetNmul(i);
aSequence[Ncustom-1-i] = divide;
}
}
return aSequence;
}
public static int GetNmul(int n)
{
if (n == 0)
return 1;
else
return n * GetNmul(n - 1);
}
public static void PrintPath(int [] aPath)
{
for (int i =0; i <aPath.Length; i++)
{
System.Console.Write("{0} :", aPath[i]);
}
System.Console.WriteLine("");
}
public static int[] Convertsequence(int [] inArray)
{
int[] decodeArray = new int[(int)inArray.Length];
List<int> naturalList = new List<int>();
for (int i = 0; i < inArray.Length;i++)
{
naturalList.Add(i);
}
// Decoding
for (int i = 0; i < inArray.Length; i++)
{
decodeArray[i] = naturalList[inArray[i]];
naturalList.Remove(decodeArray[i]);
}
return decodeArray;
}
public static double CalDistance(int[] iPath, int[,] XYLocation, int[,] xyHome, int[,] xyOffice)
{
double dis =0, dis_0,dis_N;
for (int i = 0; i < iPath.Length-1 ; i++)
{
dis = dis + Math.Abs(XYLocation[iPath[i], 0] - XYLocation[iPath[i+1], 0])
+ Math.Abs(XYLocation[iPath[i], 1] - XYLocation[iPath[i+1], 1]);
}
dis_0 = Math.Abs(xyOffice[0,0] - XYLocation[iPath[0], 0])
+ Math.Abs(xyOffice[0,1] - XYLocation[iPath[0], 1]);
dis_N = Math.Abs(XYLocation[iPath[iPath.Length - 1], 0] - xyHome[0,0])
+ Math.Abs(XYLocation[iPath[iPath.Length - 1], 1] - xyHome[0, 1]);
dis = dis + dis_0 + dis_N;
return dis;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/* <Program description>
*
* Mr. Kim has to deliver samples to N costumer.
* Find the shortest way to deliver it and return his home
*
* Mr.Kim<Office>--> Costumer1-->....CustomerN--> His Home.
*
*
*
*/
/* <Idea --> Solution>
*
* find all possible path:
* There is N!-1 possible path
*
* for : earch path from 1----> N!-1
* (i)--> Corresponding sequence --> {Permuation}
* --> determine Shortest distance and print "the path sequence"
*
*/
/* <Result >
*
* Case #1: 200: path -> Office->[2-1-4-0-3]-->Home
* Case #2: 304: path-> Office->[1-3-5-0-4-2]-->Home
* Case #3: 366: path-> Office->[6-3-9-4-8-0-5-1-7-2]-->Home
*/
namespace ShortestPathDelivery
{
class Program
{
static void Main(string[] args)
{
// Test case:
// Case 1:
/*
const int N = 5;
int[,] xyLocation = {{ 70, 40 }, { 30, 10 }, { 10, 5 }, { 90, 70 }, { 50, 20 }};
int[,] xyOffice = { {0,0}};
int[,] xyHome = { { 100, 100 } };
*
*/
//case 2:
/*
const int N = 6;
int[,] xyLocation = { { 19, 22 }, { 31, 15 }, { 27, 29 }, { 30, 10 }, { 20, 26 },{5,14} };
int[,] xyOffice = { { 81, 88} };
int[,] xyHome = { { 85, 80 } };
*/
const int N = 10;
int[,] xyLocation = { {35,93 }, { 62,64 }, { 96,39}, { 36,36 }, { 5,59 },
{59,96},{61,7},{64,43},{43,58},{1,36} };
int[,] xyOffice = { {39,9}};
int[,] xyHome = { { 97, 61 } };
int[] pathseq = new int[N];
int[] finalPath = new int[N];
int[] shortestPath = new int[N];
double dis_Min = 10000 ;
// pathseq = GetPathsequence(2982, N);
//List allpath
for (int i = 0; i < GetNmul(N); i++)
{
pathseq = GetPathsequence(i, N);
// PrintPath(pathseq);
finalPath = Convertsequence(pathseq);
// PrintPath(finalPath);
// Calculate corresponding distance
double tempDis = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
// System.Console.Write(" --Dis: {0} ", CalDistance(finalPath, xyLocation, xyHome, xyOffice));
if (i == 0)
{
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
else
{
if (dis_Min > CalDistance(finalPath, xyLocation, xyHome, xyOffice))
{
shortestPath = finalPath;
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
}
}
PrintPath(shortestPath);
System.Console.WriteLine(" Shortest Dis: {0} ", dis_Min);
System.Console.ReadKey();
}
// This function return the sequence from n--> factorized sequence.
public static int[] GetPathsequence(int n, int Ncustom)
{
int[] aSequence = new int[Ncustom];
int divide = 0;
int remainder = 0;
for (int i = Ncustom-1; i >=0;i-- )
{
if(i==Ncustom-1)
{
divide = (int)n / GetNmul(Ncustom-1);
remainder = (int)n % GetNmul(Ncustom-1);
aSequence[Ncustom-1-i] = divide;
}
else
{
divide = remainder / GetNmul(i);
remainder = remainder % GetNmul(i);
aSequence[Ncustom-1-i] = divide;
}
}
return aSequence;
}
public static int GetNmul(int n)
{
if (n == 0)
return 1;
else
return n * GetNmul(n - 1);
}
public static void PrintPath(int [] aPath)
{
for (int i =0; i <aPath.Length; i++)
{
System.Console.Write("{0} :", aPath[i]);
}
System.Console.WriteLine("");
}
public static int[] Convertsequence(int [] inArray)
{
int[] decodeArray = new int[(int)inArray.Length];
List<int> naturalList = new List<int>();
for (int i = 0; i < inArray.Length;i++)
{
naturalList.Add(i);
}
// Decoding
for (int i = 0; i < inArray.Length; i++)
{
decodeArray[i] = naturalList[inArray[i]];
naturalList.Remove(decodeArray[i]);
}
return decodeArray;
}
public static double CalDistance(int[] iPath, int[,] XYLocation, int[,] xyHome, int[,] xyOffice)
{
double dis =0, dis_0,dis_N;
for (int i = 0; i < iPath.Length-1 ; i++)
{
dis = dis + Math.Abs(XYLocation[iPath[i], 0] - XYLocation[iPath[i+1], 0])
+ Math.Abs(XYLocation[iPath[i], 1] - XYLocation[iPath[i+1], 1]);
}
dis_0 = Math.Abs(xyOffice[0,0] - XYLocation[iPath[0], 0])
+ Math.Abs(xyOffice[0,1] - XYLocation[iPath[0], 1]);
dis_N = Math.Abs(XYLocation[iPath[iPath.Length - 1], 0] - xyHome[0,0])
+ Math.Abs(XYLocation[iPath[iPath.Length - 1], 1] - xyHome[0, 1]);
dis = dis + dis_0 + dis_N;
return dis;
}
}
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=10;
while(t--)
{
int n;
scanf("%d",&n);
vector< pair<int,int> > v;
int x1;
int y1;
cin>>x1>>y1;
int x2;
int y2;
cin>>x2;
cin>>y2;
v.push_back(make_pair(x1,y1));
for(int i=1;i<=n;i++)
{
int x;
int y;
cin>>x;
cin>>y;
v.push_back(make_pair(x,y));
}
int count=0;
v.push_back(make_pair(x2,y2));
//int dis=INT_MAX;
int k1=0;
sort(v.begin()+1,v.end()-1);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
while(next_permutation(v.begin()+1,v.end()-1))
{
int k=0;
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
if(k<k1)
{
k1=k;
}
}
// cout<<v.size()<<"\n";
cout<<k1<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=10;
while(t--)
{
int n;
scanf("%d",&n);
vector< pair<int,int> > v;
int x1;
int y1;
cin>>x1>>y1;
int x2;
int y2;
cin>>x2;
cin>>y2;
v.push_back(make_pair(x1,y1));
for(int i=1;i<=n;i++)
{
int x;
int y;
cin>>x;
cin>>y;
v.push_back(make_pair(x,y));
}
int count=0;
v.push_back(make_pair(x2,y2));
//int dis=INT_MAX;
int k1=0;
sort(v.begin()+1,v.end()-1);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
while(next_permutation(v.begin()+1,v.end()-1))
{
int k=0;
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
if(k<k1)
{
k1=k;
}
}
// cout<<v.size()<<"\n";
cout<<k1<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=10;
while(t--)
{
int n;
scanf("%d",&n);
vector< pair<int,int> > v;
int x1;
int y1;
cin>>x1>>y1;
int x2;
int y2;
cin>>x2;
cin>>y2;
v.push_back(make_pair(x1,y1));
for(int i=1;i<=n;i++)
{
int x;
int y;
cin>>x;
cin>>y;
v.push_back(make_pair(x,y));
}
int count=0;
v.push_back(make_pair(x2,y2));
//int dis=INT_MAX;
int k1=0;
sort(v.begin()+1,v.end()-1);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
while(next_permutation(v.begin()+1,v.end()-1))
{
int k=0;
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
if(k<k1)
{
k1=k;
}
}
// cout<<v.size()<<"\n";
cout<<k1<<endl;
}
return 0;
}
#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
visited[pos]=1;
if(n==total+1 && pos==1)
{
if(ans==-1)
{
ans=s;
}
else
{
ans=min(ans,s);
}
}
for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
fun(i,total+1,s+sum);
}
}
visited[pos]=0;
}
int main()
{
int t;
cin>>t;
// cout<<t<<endl;
while(t--)
{
// int n;
cin>>n;
n=n+2;
ans=-1;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
visited[i]=0;
}
fun(0,0,0);
cout<<ans<<endl;
}
return 0;
}
#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
visited[pos]=1;
if(n==total+1 && pos==1)
{
if(ans==-1)
{
ans=s;
}
else
{
ans=min(ans,s);
}
}
for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
fun(i,total+1,s+sum);
}
}
visited[pos]=0;
}
int main()
{
int t;
cin>>t;
// cout<<t<<endl;
while(t--)
{
// int n;
cin>>n;
n=n+2;
ans=-1;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
visited[i]=0;
}
fun(0,0,0);
cout<<ans<<endl;
}
return 0;
}
#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
visited[pos]=1;
if(n==total+1 && pos==1)
{
if(ans==-1)
{
ans=s;
}
else
{
ans=min(ans,s);
}
}
for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
fun(i,total+1,s+sum);
}
}
visited[pos]=0;
}
int main()
{
int t;
cin>>t;
// cout<<t<<endl;
while(t--)
{
// int n;
cin>>n;
n=n+2;
ans=-1;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
visited[i]=0;
}
fun(0,0,0);
cout<<ans<<endl;
}
return 0;
}
#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
int n,i,c,x1,y1;
scanf("%d",&n);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
int a[n];
for(i=0;i<n;i++)
a[i]=0;
for(i=0;i<n;i++)
{
a[i]=1;
c=abs(x1-x[i])+abs(y1-y[i]);
solve(a,c,n,i);
a[i]=0;
}
printf("%d\n",min);
return 0;
}
void solve(int a[],int c,int n,int p)
{
int s=0,s2,i;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=1;
solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
a[i]=0;
}
}
for(i=0;i<n;i++)
s=s+a[i];
if(s==n)
{
s2=c+abs(x[p]-x2)+abs(y[p]-y2);
if(min>s2)
min=s2;
return;
}
}
#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
int n,i,c,x1,y1;
scanf("%d",&n);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
int a[n];
for(i=0;i<n;i++)
a[i]=0;
for(i=0;i<n;i++)
{
a[i]=1;
c=abs(x1-x[i])+abs(y1-y[i]);
solve(a,c,n,i);
a[i]=0;
}
printf("%d\n",min);
return 0;
}
void solve(int a[],int c,int n,int p)
{
int s=0,s2,i;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=1;
solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
a[i]=0;
}
}
for(i=0;i<n;i++)
s=s+a[i];
if(s==n)
{
s2=c+abs(x[p]-x2)+abs(y[p]-y2);
if(min>s2)
min=s2;
return;
}
}
#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
int n,i,c,x1,y1;
scanf("%d",&n);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
int a[n];
for(i=0;i<n;i++)
a[i]=0;
for(i=0;i<n;i++)
{
a[i]=1;
c=abs(x1-x[i])+abs(y1-y[i]);
solve(a,c,n,i);
a[i]=0;
}
printf("%d\n",min);
return 0;
}
void solve(int a[],int c,int n,int p)
{
int s=0,s2,i;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=1;
solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
a[i]=0;
}
}
for(i=0;i<n;i++)
s=s+a[i];
if(s==n)
{
s2=c+abs(x[p]-x2)+abs(y[p]-y2);
if(min>s2)
min=s2;
return;
}
}
int abs(int i,int j){
if(i-j>0)
return i-j;
else
return j-i;
}
int vist(vector< pair<int , int > > cust,pair<int ,int > home,vector<bool> vis,int i){
int max=9999;
int flag=1;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
flag=0;
vis[j]=true;
int temp = abs(cust[j].first,cust[i].first)+abs(cust[j].second,cust[i].second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
if(flag==1){
return abs(cust[i].first,home.first)+abs(cust[i].second,home.second);
}
else return max;
}
int location (pair<int ,int > off ,vector< pair<int , int > > cust ,pair<int ,int > home){
vector<bool> vis(cust.size(),false);
int max=9999;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
vis[j]=true;
int temp = abs(cust[j].first,off.first)+abs(cust[j].second,off.second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
return max;
}
int main(){
pair<int ,int > off (88,81);
pair<int ,int > home (85,80);
vector<pair<int ,int > > cust;
cust.push_back(make_pair(19,22));
cust.push_back(make_pair(31,15));
cust.push_back(make_pair(27,29));
cust.push_back(make_pair(30,10));
cust.push_back(make_pair(20,26));
cust.push_back(make_pair(5,14));
cout<<location(off,cust,home);
}
int abs(int i,int j){
if(i-j>0)
return i-j;
else
return j-i;
}
int vist(vector< pair<int , int > > cust,pair<int ,int > home,vector<bool> vis,int i){
int max=9999;
int flag=1;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
flag=0;
vis[j]=true;
int temp = abs(cust[j].first,cust[i].first)+abs(cust[j].second,cust[i].second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
if(flag==1){
return abs(cust[i].first,home.first)+abs(cust[i].second,home.second);
}
else return max;
}
int location (pair<int ,int > off ,vector< pair<int , int > > cust ,pair<int ,int > home){
vector<bool> vis(cust.size(),false);
int max=9999;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
vis[j]=true;
int temp = abs(cust[j].first,off.first)+abs(cust[j].second,off.second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
return max;
}
int main(){
pair<int ,int > off (88,81);
pair<int ,int > home (85,80);
vector<pair<int ,int > > cust;
cust.push_back(make_pair(19,22));
cust.push_back(make_pair(31,15));
cust.push_back(make_pair(27,29));
cust.push_back(make_pair(30,10));
cust.push_back(make_pair(20,26));
cust.push_back(make_pair(5,14));
cout<<location(off,cust,home);
}
#include<bits/stdc++.h>
using namespace std;
class coords{
public:
int x;
int y;
};
coords off,home;
coords cust[10];
bool vis[10];
int cVisit(int i,int n){
int max1=99999;
int flag=1;
for(int j=0;j<n;j++)
{
if(!vis[j])
{
flag=0;
vis[j]=true;
int temp=abs(cust[i].x-cust[j].x)+abs(cust[i].y-cust[j].y)+cVisit(j,n);
vis[j]=false;
if(temp<max1){max1=temp;}
}
}
if(flag==1){return abs(cust[i].x-home.x)+abs(cust[i].y-home.y);}
else{return max1;}
}
int func(int n){
for(int i=0;i<n;i++)
vis[i]=false;
int max=99999;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i]=true;
int temp=abs(cust[i].x-off.x)+abs(cust[i].y-off.y)+cVisit(i,n);
vis[i]=false;
if(temp<max){max=temp;}
}
}
return max;
}
int main(){
int t;
while(t--){
int n;
cin>>n;
cin>>off.x>>off.y;
cin>>home.x>>home.y;
for(int i=0;i<n;i++)
cin>>cust[i].x>>cust[i].y;
cout<<func(n)<<endl;
}
}
Backtracking approach :
import java.util.Scanner;
public class Other {
public static void main(String[] args) {
int t = 10;
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
while (t != 0) {
int n = sc.nextInt();
int x[] = new int[n + 2];
int y[] = new int[n + 2];
x[0] = sc.nextInt();
y[0] = sc.nextInt();
x[n + 1] = sc.nextInt();
y[n + 1] = sc.nextInt();
for (int i = 1; i <= n; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
n = n + 2;
boolean[] visited = new boolean[n];
min = Integer.MAX_VALUE;
compute(visited, 0, 0, n - 1, x, y, 0);
System.out.println(min);
t--;
}
}
public static int min;
private static void compute(boolean[] visited, int i, int d, int n, int[] x, int[] y, int vv) {
if (vv == (n - 1)) {
int k = Math.abs(x[i] - x[n]) + Math.abs(y[i] - y[n]);
if ((d + k) < min) {
min = d + k;
}
return;
}
if (!visited[i]) {
visited[i] = true;
for (int k = 0; k < n; k++) {
if (!visited[k]) {
d = d + (Math.abs(x[i] - x[k]) + Math.abs(y[i] - y[k]));
vv += 1;
compute(visited, k, d, n, x, y, vv);
vv -= 1;
d = d - (Math.abs(x[i] - x[k]) + Math.abs(y[i] - y[k]));
visited[k] = false;
}
}
}
}
}
import java.util.Scanner;
import java.lang.Math;
class GFG {
static class pair
{
int x,y;
public pair(int x,int y)
{
this.x=x;
this.y=y;
}
}
static class mind
{
static int d=Integer.MAX_VALUE;
}
void swap(pair ar[],int x,int y)
{
pair temp=ar[x];
ar[x]=ar[y];
ar[y]=temp;
}
int calcDist(pair o,pair h,pair[] c)
{
int l=c.length;
int sum=0;
sum+=Math.abs(o.x-c[0].x)+Math.abs(o.y-c[0].y);
for(int i=0;i<l-1;i++)
{
sum+=Math.abs(c[i].x-c[i+1].x)+Math.abs(c[i].y-c[i+1].y);
}
sum+=Math.abs(c[l-1].x-h.x)+Math.abs(c[l-1].y-h.y);
return sum;
}
public void bctrack(pair o,pair h,pair a[],int l, int hi)
{
if(l==hi)
{
int d=calcDist(o,h,a);
mind.d=Math.min(d,mind.d);
return;
}
for(int i=l;i<=hi;i++)
{
swap(a,l,i);
bctrack(o,h,a,l+1,hi);
swap(a,l,i);
}
}
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
GFG ob=new GFG();
int tt=0;
while(t-->0)
{
tt++;
mind.d=Integer.MAX_VALUE;
int n=sc.nextInt();
pair[] customers=new pair[n];
pair off=new pair(sc.nextInt(),sc.nextInt());
pair home=new pair(sc.nextInt(),sc.nextInt());
for(int i=0;i<n;i++)
{
customers[i]=new pair(sc.nextInt(),sc.nextInt());
}
ob.bctrack(off,home,customers,0,n-1);
System.out.println("#"+tt+" "+mind.d);
}
}
}
}
import java.util.Scanner;
import java.lang.Math;
class GFG {
static class pair
{
int x,y;
public pair(int x,int y)
{
this.x=x;
this.y=y;
}
}
static class mind
{
static int d=Integer.MAX_VALUE;
}
void swap(pair ar[],int x,int y)
{
pair temp=ar[x];
ar[x]=ar[y];
ar[y]=temp;
}
int calcDist(pair o,pair h,pair[] c)
{
int l=c.length;
int sum=0;
sum+=Math.abs(o.x-c[0].x)+Math.abs(o.y-c[0].y);
for(int i=0;i<l-1;i++)
{
sum+=Math.abs(c[i].x-c[i+1].x)+Math.abs(c[i].y-c[i+1].y);
}
sum+=Math.abs(c[l-1].x-h.x)+Math.abs(c[l-1].y-h.y);
return sum;
}
public void bctrack(pair o,pair h,pair a[],int l, int hi)
{
if(l==hi)
{
int d=calcDist(o,h,a);
mind.d=Math.min(d,mind.d);
return;
}
for(int i=l;i<=hi;i++)
{
swap(a,l,i);
bctrack(o,h,a,l+1,hi);
swap(a,l,i);
}
}
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
GFG ob=new GFG();
int tt=0;
while(t-->0)
{
tt++;
mind.d=Integer.MAX_VALUE;
int n=sc.nextInt();
pair[] customers=new pair[n];
pair off=new pair(sc.nextInt(),sc.nextInt());
pair home=new pair(sc.nextInt(),sc.nextInt());
for(int i=0;i<n;i++)
{
customers[i]=new pair(sc.nextInt(),sc.nextInt());
}
ob.bctrack(off,home,customers,0,n-1);
System.out.println("#"+tt+" "+mind.d);
}
}
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long
#define nodes 100001
#define level 18 // ceil(log2(nodes))
#define N 15000005
using namespace std;
int n;
vector<pair<int,int>>arr;
pair<int,int>start,endd;
map<pair<int,int>,bool>visited;
int ans = INT_MAX;
void dfs(pair<int,int>&x , pair<int,int>&prev, int cost)
{
visited[x]=1;
//cout<<cost<<" ";
bool flag = 1;
if(start != x) cost += abs(x.first - prev.first) + abs(x.second - prev.second);
for(int i=0;i<n;i++)
{
if(!visited[arr[i]])
{
flag = 0;
dfs(arr[i] , x , cost);
visited[arr[i]] = 0;
}
}
cost +=abs(endd.first - x.first) + abs(endd.second - x.second);
if(flag) ans = min(ans,cost); //, cout<<cost<<" ";
//cout<<"\n\n\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
int x,y;
cin>>x>>y;
start = mp(x,y);
cin>>x>>y;
endd = mp(x,y);
for(int i=1;i<=n;i++)
{
cin>>x>>y;
arr.pb(mp(x,y));
}
pair<int,int>prev;
prev = mp(0,0);
dfs(start,prev,0);
cout<<ans;
return 0;
}
#include<iostream>
using namespace std;
int G[11][11];
int min(int a,int b){
if(a<b)
return a;
return b;
}
int ans=10000000;
void dfs(int node,int mask,int cost,int n,int len){
len++;
mask=mask|(1<<node);
if(len==n+1){
ans=min(ans,cost+G[node][n+1]);
return;
}
for(int i=0;i<=n;i++){
if(!(mask&(1<<i))){
dfs(i,mask,cost+G[node][i],n,len);
}
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
ans=1e9;
int x[n+2],y[n+2];
cin>>x[0]>>y[0];
cin>>x[n+1]>>y[n+1];
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=0;i<=(n+1);i++){
for(int j=0;j<=(n+1);j++){
G[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
}
}
dfs(0,0,0,n,0);
cout<<ans<<endl;
}
}
//Backtracking Solution
import java.io.*;
import java.util.*;
class GFG {
static class pair{
int x,y;
public pair(int a,int b)
{
x=a;
y=b;
}
}
public static boolean check(boolean visited[])
{
for(int i=1;i<visited.length;i++)
{
if(visited[i]==false)
return false;
}
return true;
}
public static int helper(ArrayList<pair> list,pair src,pair dest,int dist,boolean visited[])
{
if((src.x==dest.x&&src.y==dest.y)&&check(visited))
{
return dist;
}
else if(src.x==dest.x&&src.y==dest.y)
{
return Integer.MAX_VALUE;
}
int min=Integer.MAX_VALUE;
for(int i=1;i<visited.length;i++)
{
if(!visited[i])
{
visited[i]=true;
int a=Math.abs(src.x-list.get(i).x)+Math.abs(src.y-list.get(i).y);
int num=helper(list,list.get(i),dest,dist+a,visited);
visited[i]=false;
min=Math.min(num,min);
}
}
return min;
}
public static void main (String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
n+=2;
ArrayList<pair> list=new ArrayList<pair>();
for(int i=0;i<n;i++)
{
int a=s.nextInt();
int b=s.nextInt();
pair p=new pair(a,b);
list.add(p);
}
pair src=list.get(0);
pair dest=list.get(1);
boolean visited[]=new boolean[n];
visited[0]=true;
int ans=helper(list,src,dest,0,visited);
System.out.println(ans);
}
}
{#include <iostream>
#pragma warning (disable:4996)
using namespace std;
int mindist = 999999;
int home_x,home_y;
int x_cord[11];
int y_cord[11];
int visited[11];
int sum(int sx, int sy, int dx, int dy)
{
int x = (sx > dx) ? sx - dx : dx - sx;
int y = (sy > dy) ? sy - dy : dy - sy;
return (x + y);
}
void findall(int count, int x, int y,int n, int dis)
{
if (dis > mindist)
return;
if (count == n)
{
dis += sum(x, y, home_x, home_y);
if (dis < mindist)
{
mindist = dis;
}
return;
}
for (int i = 0; i < n; i++)
{
if (visited[i] == 0)
{
visited[i] = 1;
dis += sum(x, y, x_cord[i], y_cord[i]);
findall(count + 1, x_cord[i], y_cord[i], n,dis);
dis -= sum(x, y, x_cord[i], y_cord[i]);
visited[i] = 0;
}
}
}
int main(int argc, char** argv)
{
int T, test, n,office_x,office_y;
freopen("input.txt", "r", stdin);
cin >> T;
for (test = 0; test < T; test++)
{
mindist = 999999;
cin >> n;
cin >> office_x >> office_y >> home_x >> home_y;
for (int i = 0; i < n; i++)
{
cin >> x_cord[i] >> y_cord[i];
visited[i] = 0;
}
findall(0, office_x, office_y, n, 0);
cout << mindist << endl;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TSPBitMask {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=12;
int dist[][]=new int[n][n];
ArrayList<Integer> xy=new ArrayList();
xy.addAll(Arrays.asList(39,9,35,93,62,64,96,39,36,36,9,59,59,96,61,7,64,43,43,58,1,36,97,61));
ArrayList<Integer> x=new ArrayList();
ArrayList y=new ArrayList<>();
for(int i=0;i<xy.size();i++) {
if (i % 2 == 0) {
x.add(xy.get(i));
}
else {
y.add(xy.get(i));
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
dist[i][j]=Math.abs((int)x.get(i)-(int)x.get(j))+Math.abs((int)y.get(i)-(int)y.get(j));
}
}
int bitmask=1;
int index=0;
ArrayList<Integer> path=new ArrayList<>();
int ans=mst(dist,bitmask,index,n,path);
System.out.println(ans);
path.stream().forEach(System.out::println);
}
public static int mst(int[][] dist,int bitmask,int index,int n,ArrayList path)
{
if(bitmask==(1<<n-1)-1)
{
return dist[index][n-1];
}
int minCost=Integer.MAX_VALUE;
int cost=0;
for(int i=1;i<n-1;i++)
{
int bitcheck=1<<i;
if((bitcheck&bitmask)==0){
int newbitmask=bitmask|bitcheck;
ArrayList temppath=new ArrayList(path);
cost=mst(dist,newbitmask,i,n,temppath);
cost+=dist[index][i];
if(cost<minCost)
{
minCost=cost;
}
}
}
return minCost;
}
}
- Anthony September 03, 2016#include <bits/stdc++.h> using namespace std; int dp[13][1 << 12]; int x[13], y[13]; int n; int calc(int p, int mask) { if (p == 0) return (mask != 0) * 1e9; int &ret = dp[p][mask]; if (ret != -1) return ret; ret = 1e9; for (int i = 0; i <= n; ++i) { if (mask & (1 << i)) { int dist = abs(x[p] - x[i]) + abs(y[p] - y[i]); ret = min(ret, calc(i, mask ^ (1 << i)) + dist); } } return ret; } int main() { for (int i = 0; i < 10; ++i) { scanf("%d", &n); scanf("%d %d", &x[n + 1], &y[n + 1]); scanf("%d %d", &x[0], &y[0]); for (int j = 1; j <= n; ++j) { scanf("%d %d", &x[j], &y[j]); } memset(dp, -1, sizeof dp); printf("#%d %d\n", i + 1, calc(n + 1, (1 << (n + 1)) - 1)); } return 0; }