High score in grid walk

Question

There is an interesting game named one person game. It is played on a m*n grid. There is an non-negative integer in each grid cell. You start with a score of 0. You cannot enter a cell with an integer 0 in it. You can start and end the game at any cell you want (of course the number in the cell cannot be 0). At each step you can go up, down, left and right to the adjacent grid cell. The score you can get at last is the sum of the numbers on your path. But you can enter each cell at most once.

The aim of the game is to get your score as high as possible.

Input:
The first line of input is an integer T the number of test cases. The first line of each test case is a single line containing 2 integers m and n which is the number of rows and columns in the grid. Each of next the m lines contains n space-separated integers D indicating the number in the corresponding cell

Output:
For each test case output an integer in a single line which is maximum score you can get at last.

Constraints:
T is less than 7.
D is less than 60001.
m and n are less than 8.

Sample Input:

4
1 1
5911
1 2
10832 0
1 1
0
4 1
0
8955
0
11493

Sample Output:

5911
10832
0
11493

I tried it but my approach is working very slow for a 7x7 grid.I am trying to access every possible path of the grid recursively and comparing the sum of every path.Below is my code

#include<iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int max(int a,int b,int c, int d)
{
int max = a;
if(b>max)
    max = b;
if(c>max)
    max = c;
if(d>max)
    max = d;
return max;
}

int Visit_Component( int (*A)[8], int Visit[8][8], int m,int n , int row, int col)
{

if ( ( row >= m ) || (col >= n )  || (col < 0) || (row < 0)  || A[row][col] == 0         || Visit[row][col] == 1 )
{
    return 0;
}
else
{

    Visit[row][col] = 1;
    int a= 0,b=0,c=0,d=0,result =0;
    a = Visit_Component( A, Visit,m,n, row+1, col);
    b = Visit_Component( A, Visit,m,n, row, col +1);
    c = Visit_Component( A, Visit,m,n, row, col -1);
    d = Visit_Component( A, Visit,m,n, row-1, col );
    Visit[row][col] = 0;
    result  = A[row][col] + max(a,b,c,d);
    return result;
}
}

int main(){

int T;
scanf("%d",&T);
for(int k =0; k<T;k++)
{
    int N ;
    int M;
    int count = 0;
    int maxcount = 0;
    scanf("%d %d",&M,&N);
    int C[8][8];
    int visit[8][8];
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
        {
            scanf("%d",&C[i][j]);
            visit[i][j] = 0;
        }
    for( int i= 0 ; i< M ; i++ )
    {
        for( int j =0; j< N ; j++ )
        {

            count  = Visit_Component( C, visit,M,N, i, j);
            if(count > maxcount)
            {
                maxcount  = count;
            }
        }
    }
    printf("%d\n",maxcount);
}
return 0;
}

Please suggest me how to optimize this approach or a better algorithm.

Answer 1

As Wikipedia article on Travelling salesman problem suggests, there are exact algorithms, solving this task quickly. But it is hard to find any. And they are, most likely, complicated.

As for optimizing OP's approach, there are several possibilities.

It's easier to start with simple micro-optimization: condition Visit[row][col] == 1 is satisfied with highest probability, so it should come first.

Also it is reasonable to optimize branch-and-bound algorithm with dynamic programming to avoid some repeated calculations. Memorizing calculation results in simple hash table for the cases of up to 19 visited cells improves performance by more than 25% (and more may be expected for some improved hash table). Here is the modified code snippet:

#include<iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int max(int a,int b,int c, int d)
{
  int max = a;
  if(b>max)
    max = b;
  if(c>max)
    max = c;
  if(d>max)
    max = d;
  return max;
}

typedef unsigned long long ull;
static const int HS = 10000019;
static const int HL = 20;
struct HT {
  ull v;
  int r;
  int c;
};
HT ht[HS] = {0};

int Visit_Component(
  int (*A)[8], ull& Visit, int m,int n , int row, int col, int x)
{

  if ( (Visit & (1ull << (8*row+col))) || ( row >= m ) || (col >= n )  ||
    (col < 0) || (row < 0)  || A[row][col] == 0)
  {
    return 0;
  }
  else
  {
    if (x < HL)
    {
      HT& h = ht[(Visit+4*row+col)%HS];
      if (h.v == Visit && h.r == row && h.c == col)
        return 0;
    }

    Visit |= (1ull << (8*row+col));
    int a= 0,b=0,c=0,d=0,result =0;
    a = Visit_Component( A, Visit,m,n, row+1, col, x+1);
    b = Visit_Component( A, Visit,m,n, row, col +1, x+1);
    c = Visit_Component( A, Visit,m,n, row, col -1, x+1);
    d = Visit_Component( A, Visit,m,n, row-1, col , x+1);
    Visit &= ~(1ull << (8*row+col));
    result  = A[row][col] + max(a,b,c,d);

    if (x < HL)
    {
      HT& h = ht[(Visit+4*row+col)%HS];
      h.v = Visit;
      h.r = row;
      h.c = col;
    }

    return result;
  }
}

int main(){

  int T;
  scanf("%d",&T);
  for(int k =0; k<T;k++)
  {
    int N ;
    int M;
    int count = 0;
    int maxcount = 0;
    scanf("%d %d",&M,&N);
    int C[8][8];
    ull visit = 0;
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
        {
            scanf("%d",&C[i][j]);
        }
    for( int i= 0 ; i< M ; i++ )
    {
        for( int j =0; j< N ; j++ )
        {

            count  = Visit_Component( C, visit,M,N, i, j, 0);
            if(count > maxcount)
            {
                maxcount  = count;
            }
        }
    }
    printf("%d\n",maxcount);
  }
  return 0;
}

And much more improvements may be done by pre-processing the input matrix. If there are no zeros in the matrix or if there is only one zero in the corner, you may just sum all the values.

If there is only one zero value (not in the corner), at most one non-zero value should be excluded from the sum. If you invent an algorithm, that determines the subset of cells, from which one of the cells must be removed, you can just select the smallest value from this subset.

If there are two or more zero values, use branch-and-bound algorithm: in this case it is about 20 times faster, because each zero value in input matrix means approximately fivefold speed increase.

Answer 2

One optimization that I can think of is to apply Dijkstra's algorithm. This algorithm will give you a minimum (in your case maximum) path for a particular source node to all destination nodes.

In this example, the first step would be to build a graph.

And because you don't know the source node to start at, you will have to apply Dijkstra's algorithm for each node in the grid. The time complexity will be better than your recursion method because for a particular source node, when finding a maximum path Dijkstra's algorithm does not go through all the possible paths.