Travelling Salesman in a Grid – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Travelling Salesman in a Grid HackerRank Solution
//Template
#include <cstdio>
#include <climits>
#include <iostream>
#include <map>
using namespace std;
#define N 10
int n, m, now = 0, hor[N + 1][N + 1], ver[N + 1][N + 1];
map <int, int> h[2];
map <int, int> :: iterator it;
inline int get(int x, int p) { //get state of pos p from right
return x >> (p - 1 << 1) & 3;
}
inline int Set(int v, int p) {
return v << (p - 1 << 1);
}
inline void update(int x, int v) {
if (h[now].find(x) == h[now].end()) h[now][x] = v;
else h[now][x] = min(h[now][x], v);
}
void decrypt(int x) {
for (int i = 1; i <= m + 1; ++i) {
int a = x & 3;
if (a == 0) printf("#");
else if (a == 1) printf("(");
else if (a == 2) printf(")");
x >>= 2;
}
}
int main() {
#ifdef KANARI
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < m; ++j)
cin >> hor[i][j];
for (int i = 1; i < n; ++i)
for (int j = 1; j <= m; ++j)
cin >> ver[i][j];
int ans = INT_MAX;
h[now][0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
now ^= 1;
h[now].clear();
for (it = h[now ^ 1].begin(); it != h[now ^ 1].end(); ++it) {
int x = it->first, v = it->second;
// printf("i=%d j=%d ", i, j);
// decrypt(x);
// printf(" x=%d v=%d\n", x, v);
if (j == 1) x <<= 2;
int a = get(x, j), b = get(x, j + 1);
if (a == 0 && b == 0) {
if (i < n && j < m)
update(x + Set(1, j) + Set(2, j + 1), v);
} else if (a == 0 && b != 0) {
if (j < m) update(x, v + ver[i - 1][j]);
if (i < n) update(x - Set(b, j + 1) + Set(b, j), v + ver[i - 1][j]);
} else if (a != 0 && b == 0) {
if (i < n) update(x, v + hor[i][j - 1]);
if (j < m) update(x - Set(a, j) + Set(a, j + 1), v + hor[i][j - 1]);
} else if (a == 1 && b == 1) {
int k = 0, p = j + 1, c;
while (k < 1) {
c = get(x, ++p);
if (c == 1) --k;
else if (c == 2) ++k;
}
update(x - Set(1, j) - Set(1, j + 1) - Set(1, p), v + hor[i][j - 1] + ver[i - 1][j]);
} else if (a == 2 && b == 2) {
int k = 0, p = j, c;
while (k < 1) {
c = get(x, --p);
if (c == 1) ++k;
else if (c == 2) --k;
}
update(x - Set(2, j) - Set(2, j + 1) + Set(1, p), v + hor[i][j - 1] + ver[i - 1][j]);
} else if (a == 1 && b == 2) {
if (i == n && j == m) ans = min(ans, v + hor[i][j - 1] + ver[i - 1][j]);
} else if (a == 2 && b == 1) {
update(x - Set(2, j) - Set(1, j + 1), v + hor[i][j - 1] + ver[i - 1][j]);
}
}
}
if (ans == INT_MAX) cout << 0 << endl;
else cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
Java Travelling Salesman in a Grid HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int m = ni(), n = ni();
int[][] g = new int[2*m+1][2*n+1];
for(int i = 0;i < 2*m+1;i++){
Arrays.fill(g[i], -1);
}
for(int i = 0;i < m;i++){
for(int j = 0;j < n-1;j++){
g[2*i][2*j+1] = ni();
}
}
for(int j = 0;j < m-1;j++){
for(int i = 0;i < n;i++){
g[2*j+1][2*i] = ni();
}
}
if(m == 1 || n == 1 || (m%2==1 && n%2==1)){
out.println(0);
return;
}
HMG<State> dp = new HMG<State>();
State ini = new State((1L<<4*n)-1, 0, 0);
add(ini, dp);
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
HMG<State> ndp = new HMG<State>();
for(HMG.Entry<State> e : dp.table){
for(;e != null;e = e.next){
State s = e.value;
int fig0 = s.fig&7;
int figlast = s.fig>>>3*(n-1)&7;
boolean fromup = i > 0 && (fig0 == 1 || fig0 == 3 || fig0 == 5);
boolean fromleft = j > 0 && (figlast == 0 || figlast == 3 || figlast == 4);
if(fromup){
if(fromleft){
if((i == m-1 && j == n-1) || (s.clus&15) != (s.clus>>>4*(n-1)&15)) {
// 2
long xclus = s.clus>>>4|(s.clus&15)<<4*(n-1);
int xfig = s.fig>>>3|2<<3*(n-1);
int oclus = (int)(s.clus>>>4*(n-1)&15);
for(int l = 0;l < n;l++){
if((xclus>>>4*l&15) == oclus){
xclus &= ~(15L<<4*l);
xclus |= (s.clus&15)<<4*l;
}
}
int val = s.val + g[i*2-1][j*2] + g[i*2][j*2-1];
add(new State(relocate(xclus, n), xfig, val), ndp);
}
}else{
if(j < n-1){
// 0
long xclus = s.clus>>>4|(s.clus&15)<<4*(n-1);
int xfig = s.fig>>>3|0<<3*(n-1);
int val = s.val + g[i*2-1][j*2];
add(new State(relocate(xclus, n), xfig, val), ndp);
}
if(i < m-1){
// 1
long xclus = s.clus>>>4|(s.clus&15)<<4*(n-1);
int xfig = s.fig>>>3|1<<3*(n-1);
int val = s.val + g[i*2-1][j*2];
add(new State(relocate(xclus, n), xfig, val), ndp);
}
}
}else{
if(hasHidden(s.clus, n))continue;
if(fromleft){
if(j < n-1){
// 4
long xclus = s.clus>>>4|(s.clus>>>4*(n-1)&15)<<4*(n-1);
int xfig = s.fig>>>3|4<<3*(n-1);
int val = s.val + g[i*2][j*2-1];
add(new State(relocate(xclus, n), xfig, val), ndp);
}
if(i < m-1){
// 5
long xclus = s.clus>>>4|(s.clus>>>4*(n-1)&15)<<4*(n-1);
int xfig = s.fig>>>3|5<<3*(n-1);
int val = s.val + g[i*2][j*2-1];
add(new State(relocate(xclus, n), xfig, val), ndp);
}
}else{
if(i < m-1 && j < n-1){
// 3
long xclus = s.clus>>>4|11L<<4*(n-1);
int xfig = s.fig>>>3|3<<3*(n-1);
int val = s.val;
add(new State(relocate(xclus, n), xfig, val), ndp);
}
}
}
}
}
// tr(i, j, ndp.size());
// tr(ndp.values());
dp = ndp;
}
}
int min = Integer.MAX_VALUE;
for(HMG.Entry<State> e : dp.table){
for(;e != null;e = e.next){
State s = e.value;
if(s.clus == 0L){
min = Math.min(min, s.val);
}
}
}
out.println(min);
}
public static class State
{
final long clus;
final int fig;
// UR:0
// UD:1
// UL:2
// RD:3
// RL:4
// DL:5
int val;
public State(long clus, int fig, int val) {
this.clus = clus;
this.val = val;
this.fig = fig;
}
public long h()
{
long h = 1;
h = h * 1000000009 + clus;
h = h * 1000000009 + fig;
return h;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("State [clus=");
builder.append(Long.toBinaryString(clus));
builder.append(", fig=");
builder.append(Integer.toBinaryString(fig));
builder.append(", val=");
builder.append(val);
builder.append("]");
return builder.toString();
}
}
public static boolean hasHidden(long a, int n)
{
if((a&15) != 15){
for(int i = 1;i < n;i++){
if((a>>>4*i&15) == 0)return false;
}
return true;
}else{
return false;
}
}
public static boolean hasHidden(int[] a)
{
if(a[0] != -1){
for(int i = 1;i < a.length;i++){
if(a[i] == 0)return false;
}
return true;
}else{
return false;
}
}
public static int has(int[] a)
{
for(int v : a){
if(v != -1)return 1;
}
return 0;
}
public static int num(int[] a)
{
int num = -1;
for(int v : a){
if(v > num)num = v;
}
return num+1;
}
public static long relocate(long a, int n)
{
long map = -1L;
int p = 0;
long b = 0;
for(int i = 0;i < n;i++){
int cl = (int)(a>>>4*i&15);
if(cl == 15){
b |= 15L<<4*i;
}else{
if((map>>>4*cl&15) == 15){
map ^= (15L^p++)<<4*cl;
}
b |= (map>>>4*cl&15)<<4*i;
}
}
return b;
}
public static class HMG<T> {
public int size;
private List<Entry<T>> table;
private int threshold;
static final int DEFAULT_INITIAL_CAPACITY = 4;
public HMG() {
this(DEFAULT_INITIAL_CAPACITY);
}
public HMG(int ice)
{
int capacity = 1<<ice;
threshold = capacity * 3 / 4;
table = new ArrayList<Entry<T>>();
for(int i = 0;i < capacity;i++)table.add(null);
}
final int hash(long n)
{
n ^= (n>>>20)^(n>>>12);
return (int)(n^(n>>>7)^(n>>>4));
}
int indexFor(int h, int length){
return h&length-1;
}
Entry<T> getEntry(long k)
{
for(Entry<T> e = table.get(indexFor(hash(k), table.size())); e != null; e = e.next)if(e.key == k)return e;
return null;
}
T get(long k)
{
for(Entry<T> e = table.get(indexFor(hash(k), table.size())); e != null; e = e.next)if(e.key == k)return e.value;
return null;
}
boolean containsKey(long k)
{
for(Entry<T> e = table.get(indexFor(hash(k), table.size())); e != null; e = e.next)if(e.key == k)return true;
return false;
}
T put(long k, T v)
{
int h = hash(k);
int i = indexFor(h, table.size());
for(Entry<T> e = table.get(i); e != null; e = e.next){
if(e.key == k){
T oldValue = e.value;
e.value = v;
return oldValue;
}
}
addEntry(h, k, v, i);
return null;
}
void addEntry(int h, long k, T v, int bucketIndex)
{
if(size >= threshold && null != table.get(bucketIndex)){
resize(2*table.size());
bucketIndex = indexFor(h, table.size());
}
createEntry(k, v, bucketIndex);
}
void resize(int nc)
{
List<Entry<T>> newTable = new ArrayList<Entry<T>>();
for(int i = 0;i < nc;i++)newTable.add(null);
transfer(newTable);
table = newTable;
threshold = nc*3/4;
}
void transfer(List<Entry<T>> newTable)
{
int nc = newTable.size();
for(Entry<T> e : table){
while(e != null){
Entry<T> next = e.next;
int i = indexFor(hash(e.key), nc);
e.next = newTable.get(i);
newTable.set(i, e);
e = next;
}
}
}
void createEntry(long k, T v, int bucketIndex)
{
Entry<T> e = table.get(bucketIndex);
table.set(bucketIndex, new Entry<T>(k, v, e));
size++;
}
// not verified
final Entry<T> remove(int k)
{
int h = hash(k);
int i = indexFor(h, table.size());
Entry<T> prev = table.get(i), e = prev;
while(e != null){
Entry<T> next = e.next;
if(e.key == k){
size--;
if(prev == e){
table.set(i, next);
}else{
prev.next = next;
}
return e;
}
prev = e;
e = next;
}
return e;
}
static class Entry<T>
{
public long key;
public T value;
public Entry<T> next;
public Entry(long key, T value, Entry<T> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}
public static HMG<State> add(State s, HMG<State> map)
{
long h = s.h();
if(map.containsKey(h)){
map.get(h).val = Math.min(map.get(h).val, s.val);
}else{
map.put(h, s);
}
return map;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Travelling Salesman in a Grid HackerRank Solution
INF = 10 ** 9
m = True, False, None
TT, TF, TN, FT, FF, FN, NT, NF, NN = ((i, j) for i in m for j in m)
m, n = map(int, input().split())
row = [list(map(int, input().split())) for i in range(m)]
column = [list(map(int, input().split())) for j in range(m - 1)]
def minimize(t, v):
global current, INF
current[t] = min(v, current.get(t, INF))
if m & n & 1:
ans = 0
else:
ans = INF
previous, current = {}, {NN[:1] * (m + n): 0}
for i in range(m):
for j in range(n):
previous, current, k = current, {}, m + j - 1 - i
for state, value in previous.items():
l, x, r = state[:k], state[k: k + 2], state[k + 2:]
if x == NN:
if i + 1 < m and j + 1 < n:
minimize(l + TF + r, value)
elif x == NT or x == NF:
value += column[i - 1][j]
if j + 1 < n:
minimize(state, value)
if i + 1 < m:
minimize(l + x[::-1] + r, value)
elif x == FN or x == TN:
value += row[i][j - 1]
if j + 1 < n:
minimize(l + x[::-1] + r, value)
if i + 1 < m:
minimize(state, value)
else:
value += row[i][j - 1] + column[i - 1][j]
if x == TF:
if i + 1 == m and j + 1 == n:
ans = min(ans, value)
elif x == FT:
minimize(l + NN + r, value)
elif x == TT:
count = 1
index = -1
while count:
index += 1
count += 1 if r[index] == TT[0] else -1 if r[index] == FF[0] else 0
minimize(l + NN + r[:index] + TT[:1] + r[index + 1:], value)
else:
count = -1
index = k
while count:
index -= 1
count += 1 if l[index] == TT[0] else -1 if l[index] == FF[0] else 0
minimize(l[:index] + FF[:1] + l[index + 1:] + NN + r, value)
print(ans)
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
