HackerRank Travelling Salesman in a Grid Solution

Yashwant Parihar,

In this post, we will solve HackerRank Travelling Salesman in a Grid Problem Solution.

The travelling salesman has a map containing m*n squares. He starts from the top left corner and visits every cell exactly once and returns to his initial position (top left). The time taken for the salesman to move from a square to its neighbor might not be the same. Two squares are considered adjacent if they share a common edge and the time taken to reach square b from square a and vice-versa are the same. Can you figure out the shortest time in which the salesman can visit every cell and get back to his initial position?

Input Format

The first line of the input is 2 integers m and n separated by a single space. m and n are the number of rows and columns of the map.
Then m lines follow, each of which contains (n – 1) space separated integers. The jth integer of the ith line is the travel time from position (i,j) to (i,j+1) (index starts from 1.)
Then (m-1) lines follow, each of which contains n space integers. The jth integer of the ith line is the travel time from position (i,j) to (i + 1, j).

Constraints

1 ≤ m, n ≤ 10
Times are non-negative integers no larger than 10000.

Output Format

Just an integer contains the minimal time to complete his task. Print 0 if its not possible to visit each cell exactly once.

Sample Input

2 2
5
8
6 7

Sample Output

26

Explanation

As its a 2*2 square, all cells are visited. 5 + 7 + 8 + 6 = 26

HackerRank Travelling Salesman in a Grid Problem Solution
HackerRank Travelling Salesman in a Grid Problem Solution

Travelling Salesman in a Grid C Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

struct betweenrows{
    int *vertedge;
    int edgemask;
    int numpairs;
    int *pairpos[2];
    int *pairnum;
    int *conto;
};

void printbet(struct betweenrows toprint, int n){
    for(int i = 0; i < n; i++){
        switch(toprint.vertedge[i]){
            case 0:
                printf(".");
                break;
            case 1:
                printf("(");
                break;
            case 2:
                printf(")");
                break;
        }
    }
    printf("\n");
}

void printhoriz(int bits, int n){
    for(int i = 0; i < n - 1; i++){
        if(((bits>>i)&1) == 0){
            printf(".");
        }
        else{
            printf("_");
        }
    }
    printf("\n");
}

int tspGrid(int m, int n, int** horizontal, int** vertical) {
    //Between status given by number up to 3^n, with symbols _()
    int hamming[1<<n];
    hamming[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 1<<i; j++){
            hamming[(1<<i) + j] = 1 + hamming[j];
        }
    }

    if(n == 1 || m == 1){
        return 0;
    }
    if(((m*n)&1) == 1){
        return 0;
    }

    int pow3[n + 1];
    pow3[0] = 1;
    for(int i = 0; i < n; i++){
        pow3[i + 1] = 3*pow3[i];
    }
    int *strtobet = malloc(pow3[n]*sizeof(int));

    struct betweenrows *betlist = NULL;
    int numbets = 0;
    int currsymb[n];
    for(int i = 0; i < n; i++){
        currsymb[i] = 0;
    }
    while(true){
        bool isgood = true;
        int balance = 0;
        for(int i = 0; i < n; i++){
            if(currsymb[i] == 1){
                balance++;
            }
            else if(currsymb[i] == 2){
                balance--;
                if(balance < 0){
                    isgood = false;
                    break;
                }
            }
        }
        if(isgood && balance == 0){
            numbets++;
            betlist = realloc(betlist, numbets*sizeof(struct betweenrows));
            betlist[numbets - 1].vertedge = malloc(n*sizeof(int));
            int strnum = 0;
            betlist[numbets - 1].edgemask = 0;

            betlist[numbets - 1].numpairs = 0;
            betlist[numbets - 1].pairnum = malloc(n*sizeof(int));
            betlist[numbets - 1].pairpos[0] = NULL;
            betlist[numbets - 1].pairpos[1] = NULL;
            betlist[numbets - 1].conto = malloc(n*sizeof(int));

            int pairstack[n];
            int stacksize = 0;
            for(int a = 0; a < n; a++){
                betlist[numbets - 1].vertedge[a] = currsymb[a];
                betlist[numbets - 1].edgemask += (currsymb[a] > 0? 1<<a : 0);
                strnum += currsymb[a]*pow3[a];
                if(currsymb[a] == 0){
                    betlist[numbets - 1].pairnum[a] = -1;
                    betlist[numbets - 1].conto[a] = -1;
                }
                else if(currsymb[a] == 1){
                    betlist[numbets - 1].pairnum[a] = betlist[numbets - 1].numpairs;
                    pairstack[stacksize] = betlist[numbets - 1].numpairs;
                    betlist[numbets - 1].numpairs++;
                    betlist[numbets - 1].pairpos[0] = realloc(betlist[numbets - 1].pairpos[0], betlist[numbets - 1].numpairs*sizeof(int));
                    betlist[numbets - 1].pairpos[1] = realloc(betlist[numbets - 1].pairpos[1], betlist[numbets - 1].numpairs*sizeof(int));
                    betlist[numbets - 1].pairpos[0][betlist[numbets - 1].numpairs - 1] = a;
                    stacksize++;
                }
                else{
                    betlist[numbets - 1].pairnum[a] = pairstack[stacksize - 1];
                    betlist[numbets - 1].pairpos[1][pairstack[stacksize - 1]] = a;
                    betlist[numbets - 1].conto[a] = betlist[numbets - 1].pairpos[0][pairstack[stacksize - 1]];
                    betlist[numbets - 1].conto[betlist[numbets - 1].pairpos[0][pairstack[stacksize - 1]]] = a;
                    stacksize--;
                }
            }

            strtobet[strnum] = numbets - 1;
        }
        int i;
        for(i = 0; i < n; i++){
            currsymb[i]++;
            if(currsymb[i] != 3){
                break;
            }
            else{
                currsymb[i] = 0;
            }
        }
        if(i == n){
            break;
        }
    }


    int connections[1<<(n - 1)][n];
    for(int i = 0; i < 1<<(n - 1); i++){
        int callback = -1;
        for(int j = 0; j < n; j++){
            bool leftedge = ((i<<1)>>j)&1;
            bool rightedge = (i>>j)&1;
            if(rightedge && !leftedge){
                callback = j;
            }
            else if(leftedge && !rightedge){
                connections[i][callback] = j;
                connections[i][j] = callback;
                callback = -1;
            }
            else if(!leftedge && !rightedge){
                connections[i][j] = j;
            }
            else{
                connections[i][j] = -1;
            }
        }
    }

    int *transition[numbets];
    for(int i = 0; i < numbets; i++){
        transition[i] = malloc(sizeof(int)<<(n - 1));
        struct betweenrows currbet = betlist[i];
        int betmask = currbet.edgemask;
        for(int j = 0; j < 1<<(n - 1); j++){
            if((j & (j<<1) & betmask) != 0){//Too many edges at vertex
                transition[i][j] = -1;
                continue;
            }
            if((j | (j<<1) | betmask) != ((1<<n) - 1)){//Not enough edges at vertex
                transition[i][j] = -1;
                continue;
            }
            int nextmask = j ^ (j<<1) ^ betmask;
            //Calculating transition and checking for loops
            int transto = 0;
            /*
            int nextconnections[currbet.numpairs][2];
            for(int a = 0; a < currbet.numpairs; a++){
                nextconnections[a][0] = -1;
                nextconnections[a][1] = -1;
            }
            */
            for(int a = 0; a < n; a++){
                bool leftedge = ((j<<1)>>a)&1;
                bool rightedge = (j>>a)&1;
                bool upedge = currbet.vertedge[a];
                if(upedge && (leftedge ^ rightedge)){
                    int currpos = currbet.conto[a];
                    bool gopair = false;
                    while(currpos != a && ((nextmask>>currpos)&1) == 0){
                        if(gopair){
                            currpos = currbet.conto[currpos];
                            gopair = false;
                        }
                        else{
                            currpos = connections[j][currpos];
                            gopair = true;
                        }
                    }
                    if(currpos == a){
                        transto = -1;
                        break;
                    }
                }
                else if((upedge && !leftedge && !rightedge) || !upedge && (leftedge ^ rightedge)){
                    int currpos;
                    bool gopair;
                    if(upedge){
                        currpos = currbet.conto[a];
                        gopair = false;
                    }
                    else{
                        currpos = connections[j][a];
                        gopair = true;
                    }
                    while(((nextmask>>currpos)&1) == 0){
                        if(gopair){
                            currpos = currbet.conto[currpos];
                            gopair = false;
                        }
                        else{
                            currpos = connections[j][currpos];
                            gopair = true;
                        }
                    }
                    if(currpos < a){
                        transto += pow3[currpos] + 2*pow3[a];
                    }
                }
            }

            if(transto != -1){
                transition[i][j] = strtobet[transto];
                
                printbet(betlist[i], n);
                printhoriz(j, n);
                printbet(betlist[transition[i][j]], n);
                printf("\n");
                
            }
            else{
                transition[i][j] = -1;
            }
        }
    }
    
    int bestout[m][numbets];
    
    for(int i = 0; i < numbets; i++){
        bestout[0][i] = INT_MAX/2;
    }
    bestout[0][0] = 0;
    for(int i = 0; i < m - 1; i++){
        int vertcost[1<<n];
        vertcost[0] = 0;
        for(int j = 0; j < n; j++){
            for(int k = 0; k < 1<<j; k++){
                vertcost[(1<<j) + k] = vertcost[k] + vertical[i][j];
            }
        }
        int horcost[1<<(n - 1)];
        horcost[0] = 0;
        for(int j = 0; j < n - 1; j++){
            for(int k = 0; k < 1<<j; k++){
                horcost[(1<<j) + k] = horcost[k] + horizontal[i][j];
            }
        }
        for(int j = 0; j < numbets; j++){
            bestout[i + 1][j] = INT_MAX/2;
        }
        for(int j = 0; j < numbets; j++){
            for(int k = 0; k < 1<<(n - 1); k++){
                int nextbet = transition[j][k];
                if(nextbet != -1){
                    int check = bestout[i][j] + horcost[k] + vertcost[betlist[nextbet].edgemask];
                    bestout[i + 1][nextbet] = (check < bestout[i + 1][nextbet]? check : bestout[i + 1][nextbet]);
                }
            }
        }

        for(int j = 0; j < numbets; j++){
            if(bestout[i + 1][j] < INT_MAX/2){
                printbet(betlist[j], n);
                printf("%d\n", bestout[i + 1][j]);
            }
        }
        printf("\n");
    }

    int best = INT_MAX/2;
    
    int horcost[1<<(n - 1)];
    horcost[0] = 0;
    for(int j = 0; j < n - 1; j++){
        for(int k = 0; k < 1<<j; k++){
            horcost[(1<<j) + k] = horcost[k] + horizontal[m - 1][j];
        }
    }
    
    for(int i = 0; i < numbets; i++){

        int hormask = 0;
        for(int a = 0; a < n; a++){
            hormask ^= betlist[i].edgemask<<a;
        }
        hormask &= (1<<n) - 1;

        if((hormask & (hormask << 1) & betlist[i].edgemask != 0)){
            continue;
        }
        if((hormask | (hormask<<1) | betlist[i].edgemask) != (1<<n) - 1){
            continue;
        }

        int a = 0;
        while(betlist[i].vertedge[a] == 0){
            a++;
        }
        int numreps = 0;
        int currpos = a;
        do{
            if(betlist[i].conto[currpos] == -1){
                numreps = -1;
                break;
            }
            currpos = connections[hormask][betlist[i].conto[currpos]];
            assert(currpos != -1);
            numreps++;
        }while(currpos != a);
        if(numreps == betlist[i].numpairs){
            int check = horcost[hormask] + bestout[m - 1][i];
            best = (check < best? check : best);
        }
    }
    
    return best;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char** mn = split_string(readline());

    char* m_endptr;
    char* m_str = mn[0];
    int m = strtol(m_str, &m_endptr, 10);

    if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

    char* n_endptr;
    char* n_str = mn[1];
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    int** horizontal = malloc(m * sizeof(int*));

    for (int horizontal_row_itr = 0; horizontal_row_itr < m; horizontal_row_itr++) {
        *(horizontal + horizontal_row_itr) = malloc((n-1) * (sizeof(int)));

        char** horizontal_item_temp = split_string(readline());

        for (int horizontal_column_itr = 0; horizontal_column_itr < n-1; horizontal_column_itr++) {
            char* horizontal_item_endptr;
            char* horizontal_item_str = *(horizontal_item_temp + horizontal_column_itr);
            int horizontal_item = strtol(horizontal_item_str, &horizontal_item_endptr, 10);

            if (horizontal_item_endptr == horizontal_item_str || *horizontal_item_endptr != '\0') { exit(EXIT_FAILURE); }

            *(*(horizontal + horizontal_row_itr) + horizontal_column_itr) = horizontal_item;
        }
    }

    int horizontal_rows = m;
    int horizontal_columns = n-1;

    int** vertical = malloc((m-1) * sizeof(int*));

    for (int vertical_row_itr = 0; vertical_row_itr < m-1; vertical_row_itr++) {
        *(vertical + vertical_row_itr) = malloc(n * (sizeof(int)));

        char** vertical_item_temp = split_string(readline());

        for (int vertical_column_itr = 0; vertical_column_itr < n; vertical_column_itr++) {
            char* vertical_item_endptr;
            char* vertical_item_str = *(vertical_item_temp + vertical_column_itr);
            int vertical_item = strtol(vertical_item_str, &vertical_item_endptr, 10);

            if (vertical_item_endptr == vertical_item_str || *vertical_item_endptr != '\0') { exit(EXIT_FAILURE); }

            *(*(vertical + vertical_row_itr) + vertical_column_itr) = vertical_item;
        }
    }

    int vertical_rows = m-1;
    int vertical_columns = n;

    int result = tspGrid(m, n, horizontal, vertical);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }
    if(data[data_length - 1] != '\0'){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

Travelling Salesman in a Grid C++ Solution

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <ctime>

using namespace std;

typedef long long ll;

class DisjointSet{
public:
    DisjointSet( int size ){
        rank.resize( size, 0 );
        p.resize( size, -1 );
        elem.resize( size, 0 );
    }
    
    void makeSet( int x ){
        p[x] = x;
        rank[x] = 0;
        elem[x] = 1;
    }

    bool isSet( int x, int y ) {
        return !( p[x]<0 || p[y]<0 );
    }

    bool Union( int x, int y ){
        if ( isSameSet(x,y) ) return false;
        link( findSet(x), findSet(y) );
        return true;
    }
    
    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }
    
    bool isSameSet( int x, int y ){
        return ( findSet(x) == findSet(y) );
    }

    vector<int> rank, p, elem;
    
    void link ( int x, int y ){
        if ( rank[x] > rank[y] ){
            p[y] = x;
            elem[x] += elem[y];
        } else {
            p[x] = y;
            elem[y] += elem[x];
            if ( rank[x] == rank[y] ) rank[y]++;
        }
    }
};

inline bool bit(ll x, ll b)
{
    return ((x>>b)&1)==1;
}

static unordered_map<ll,vector<ll>> memo;
vector<ll>& Next(int r, ll cur, bool first)
{
    if ( memo.count(cur) ) return memo[cur];

    ll w = cur&((1LL<<32)-1), g = cur>>32;
    vector<ll> next;
    for ( int i = 0; i < (1<<r); i++ ) {
        ll a = w<<1, b = i<<1;
        bool valid = true;
        for ( int j = 0; j <= r; j++ ) {
            ll a0 = a&3, b0 = b&3;
            if ( a0==0&&b0==0 || a0==3&&b0==3 || a0==1&&b0==2 || a0==2&&b0==1 ) {
                valid = false;
                break;
            }
            a>>=1;
            b>>=1;
        }
        if ( !valid ) {
            continue;
        }

        DisjointSet d(2*r);
        for ( int j = 0; j < r; j++ ) {
            if ( bit(w,j) ) d.makeSet(j);
            if ( bit(i,j) ) d.makeSet(j+r);
            if ( bit(w,j) && bit(i,j) ) {
                d.Union(j,j+r);
            }
        }

        for ( int j = 0; j < r; j++ ) {
            if ( !bit(w,j) ) continue;
            for ( int k = j+1; k < r; k++ ) {
                if ( !bit(w,k) ) continue;
                if ( ((g>>(3*j))&7) == ((g>>(3*k))&7) ) {
                    d.Union(j,k);
                }
            }
        }

        for ( int j = 1; j < r; j++ ) {
            if ( bit(i,j-1) && bit(i,j) ) {
                if ( !d.Union(j+r-1, j+r) ) {
                    valid = false;
                    break;
                }
            }
        }
        if ( !valid ) {
            continue;
        }

        bool checked[32] = {0};
        for ( int j = 0; j < r; j++ ) {
            if ( !bit(w,j) || checked[d.findSet(j)] ) continue;
            bool connedted = false;
            for ( int k = 0; k < r; k++ ) {
                if ( !bit(i,k) ) continue;
                if ( d.findSet(j) == d.findSet(k+r) ) {
                    checked[d.findSet(j)] = true;
                    connedted = true;
                    break;
                }
            }
            if ( !connedted ) {
                valid = false;
                break;
            }
        }
        if ( !valid ) {
            continue;
        }

        ll gn[16] = {0};
        int ig = 0;
        map<ll,ll> mp;
        for ( int j = 0; j < r; j++ ) {
            if ( !bit(i,j) ) continue;
            if ( mp.count(d.findSet(j+r)) ) {
                gn[j] = mp[d.findSet(j+r)];
            } else {
                mp[d.findSet(j+r)] = ig;
                gn[j] = ig;
                ig++;
            }
        }

        ll t = 0;
        for ( int j = r-1; j >= 0; j-- ) {
            t <<= 3;
            t += gn[j];
        }
        next.push_back( (t<<32) + i );
    }

    return memo[cur] = next;
}

ll Count(int r, int c)
{
    memo.clear();
    if ( r > c ) swap(r,c);

    map<ll,ll> dp;
    dp[0] = 1;
    for ( int i = 0; i < c; i++ ) {
        map<ll,ll> dp2;
        for ( auto p : dp ) {
            auto& next = Next(r, p.first, i==0);
            for ( auto nn : next ) {
                dp2[nn] += p.second;
            }
        }
        dp.swap(dp2);
    }

    ll sum = 0;
    for ( auto it = dp.begin(); it != dp.end(); ++it ) {
        ll w = it->first&((1LL<<32)-1);
        w <<= 1;
        bool valid = true;
        for ( int j = 0; j <= r; j++ ) {
            if ( (w&3) == 0 ) {
                valid = false;
                break;
            }
            w >>= 1;
        }
        if ( !valid ) {
            continue;
        }

        ll g = it->first>>32;
        if ( g ) {
            continue;
        }

        sum += it->second;
    }

    return sum;
}

ll Solve(int r, int c, vector<vector<ll>>& ch, vector<vector<ll>>& cv)
{
    memo.clear();

    map<ll,ll> dp;
    dp[0] = 0;
    for ( int i = 0; i < c; i++ ) {
        map<ll,ll> dp2;
        for ( auto p : dp ) {
            auto cur = p.first;
            for ( auto next : Next(r, cur, i==0) ) {
                ll cost = p.second;
                for ( int j = 0; j < r; j++ ) {
                    if ( bit(cur,j) ^ bit(next,j) ) {
                        cost += cv[j][i];
                    }
                }
                ll t = next<<1;
                for ( int j = 0; j <= r; j++ ) {
                    if ( bit(t,j) ^ bit(t,j+1) ) {
                        cost += ch[j][i];
                    }
                }

                if ( dp2.count(next)==0 || dp2[next] > cost ) {
                    dp2[next] = cost;
                }
            }
        }
        dp.swap(dp2);
    }

    ll ans = -1;
    for ( auto it = dp.begin(); it != dp.end(); ++it ) {
        ll w = it->first&((1LL<<32)-1);
        w <<= 1;
        bool valid = true;
        for ( int j = 0; j <= r; j++ ) {
            if ( (w&3) == 0 ) {
                valid = false;
                break;
            }
            w >>= 1;
        }
        if ( !valid ) {
            continue;
        }

        ll g = it->first>>32;
        if ( g ) {
            continue;
        }

        ll cost = it->second;
        for ( int j = 0; j < r; j++ ) {
            if ( bit(it->first,j) ) {
                cost += cv[j].back();
            }
        }

        if ( ans < 0 || ans > cost ) {
            ans = cost;
        }
    }
    if ( ans < 0 ) return 0;
    return ans;
}

int main()
{
    int n = 0, m = 0;
    cin >> m >> n;

    vector<vector<ll>> ch, cv;
    for ( int i = 0; i < m; i++ ) {
        vector<ll> v(n-1,0);
        for ( int j = 0; j < n-1; j++ ) {
            cin >> v[j];
        }
        ch.push_back(v);
    }
    for ( int i = 0; i < m-1; i++ ) {
        vector<ll> v(n,0);
        for ( int j = 0; j < n; j++ ) {
            cin >> v[j];
        }
        cv.push_back(v);
    }

    cout << Solve(m-1,n-1,ch,cv) << endl;
    return 0;
}

Travelling Salesman in a Grid Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static int[] three;

  static int bit(int s, int i) {
    return s/three[i]%3;
  }

  static final int NS = 5798;
  static int ns = 0;
  static int[] mapping = new int[177147];
  static int[] states = new int[NS];
  
  static void dfs(int k, int x, int s) {
    if (k == 0) {
      if (x == 0) {
        mapping[s] = ns;
        states[ns++] = s;
      }
      return;
    }
    dfs(k-1, x, 3*s);
    if (x > 0) {
      dfs(k-1, x-1, 3*s+1);
    }
    dfs(k-1, x+1, 3*s+2);
  }

  static int n;
  static int[] cur;
  
  static void tr(int j, int s, int g, int opt) {
    s -= three[j]*bit(s, j)+three[j+1]*bit(s, j+1);
    s += three[j]*g;
    if (j == n-1) {
      if (bit(s, n) > 0) {
        return;
      }
      s *= 3;
    }
    cur[mapping[s]] = Math.min(cur[mapping[s]], opt);
  }

  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int m = Integer.parseInt(st.nextToken());
    n = Integer.parseInt(st.nextToken());

    if (n%2 > 0 && m%2 > 0) {
      bw.write("0");
      bw.newLine();

      bw.close();
      br.close();
      return;
    }

    int[][] horizontal = new int[m > n ? m : n][n];

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < n - 1; j++) {
        int item = Integer.parseInt(st.nextToken());
        horizontal[i][j] = item;
      }
    }

    int[][] vertical = new int[m > n ? m : n][n];

    for (int i = 0; i < m - 1; i++) {
      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < n; j++) {
        int item = Integer.parseInt(st.nextToken());
        vertical[i][j] = item;
      }
    }

    three = new int[n+1];
    three[0] = 1;
    for (int i = 0; i < n; i++) {
      three[i+1] = three[i]*3;
    }
    dfs(n+1, 0, 0);

    int[][] tr4 = new int[ns][n];
    int[][] tr8 = new int[ns][n];
    for (int si = 0; si < ns; si++) {
      int s = states[si];
      for (int i = 0; i < n; i++) {
        int g = bit(s, i)+3*bit(s, i+1);
        if (g == 4) {
          int c = 0;
          for (int j = i+1; ; j++) {
            int b = bit(s, j);
            if (b == 1) c++;
            if (b == 2) c--;
            if (c == 0) {
              tr4[si][i] = s-three[i]*g-three[j]; // 1122 -> 0012
              break;
            }
          }
        }
        if (g == 8) {
          int c = 0;
          for (int j = i; ; j--) {
            int b = bit(s, j);
            if (b == 1) c++;
            if (b == 2) c--;
            if (c == 0) {
              tr8[si][i] = s-three[i]*g+three[j]; // 1122 -> 1200
              break;
            }
          }
        }
      }
    }
    
    int[][] dp = new int[2][ns];
    int[] pre = dp[0];
    cur = dp[1];
    Arrays.fill(cur, 0, ns, Integer.MAX_VALUE/2);
    cur[mapping[0]] = 0;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        int[] tmp = pre;
        pre = cur;
        cur = tmp;
        Arrays.fill(cur, 0, ns, Integer.MAX_VALUE/2);
        for (int si = 0; si < ns; si++) {
          int s = states[si];
          int g = bit(s, j)+bit(s, j+1)*3;
          int opt = pre[si];
          switch (g) {
          case 0:
            tr(j, s, 1+3*2, opt + vertical[i][j] + horizontal[i][j]);
            break;
          case 1:
          case 3:
            tr(j, s, 1, opt + vertical[i][j]);
            tr(j, s, 3, opt + horizontal[i][j]);
            break;
          case 2:
          case 6:
            tr(j, s, 2, opt + vertical[i][j]);
            tr(j, s, 6, opt + horizontal[i][j]);
            break;
          case 5:
            tr(j, s, 0, opt);
            break;
          case 4:
            tr(j, tr4[si][j], 0, opt);
            break;
          case 8:
            tr(j, tr8[si][j], 0, opt);
            break;
          case 7:
            if (i == m-1 && j == n-1)
              tr(j, s, 0, opt);
            break;
          }
        }
      }
    bw.write(String.valueOf(cur[mapping[0]]));
    bw.newLine();

    bw.close();
    br.close();
  }
}

Travelling Salesman in a Grid Python Solution

#!/bin/python3

import os
import sys

#
# Complete the tspGrid function below.
#
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)
c C++ HackerRank Solutions java python