网格行走高分

Question

有一个有趣的游戏叫一个人游戏。它在M*n网格上播放。每个网格单元格中都有一个非负整数。你从0分开始。不能输入含有整数0的单元格。你可以在你想要的任何单元格开始和结束游戏（当然单元格中的数字不能是0）。在每一步中，您可以向上、向下、向左和向右移动到相邻的网格单元格。你最后能得到的分数是你路径上的数字之和。但每个单元格最多只能输入一次。

游戏的目的是让你的分数尽可能高。

输入:
第一行输入是一个整数t测试用例的数量。每个测试用例的第一行是包含2个整数m和n，这是网格中的行和列数。接下来的M行中的每一行都包含N空格分隔的整数D，指示相应单元格中的数字

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

5911
10832
0
11493

我试过了，但是我的方法对于7x7的网格来说非常慢。我试图递归地访问网格的每一个可能的路径，并比较每一个路径的总和。下面是我的代码

#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;
}

请建议我如何优化这种方法或更好的算法。

Answer 1

正如维基百科关于旅行推销员问题的文章所建议的那样，有精确的算法，可以快速解决这个问题。但很难找到任何。它们很可能很复杂。

至于优化OP的方法，有几种可能性。

从简单的微优化开始比较容易:conditionvisite[row][col]==1满足概率最高，所以应该放在第一位。

#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;
}