HackerRank Travelling Salesman in a Grid Solution
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
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)
