网格步行高分

Question

有一个有趣的游戏名为一人游戏.它在m*n网格上播放.每个网格单元格中都有一个非负整数.您的得分为0.您不能输入整数为0的单元格.您可以在任何所需的单元格中开始和结束游戏(当然,单元格中的数字不能为0).在每个步骤中,您可以向上,向下,向左和向右移动到相邻的网格单元格.你最后得到的分数是你路径上的数字之和.但是你最多可以输入一次.

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

输入:
第一行输入是T测试用例数的整数.每个测试用例的第一行是包含2个整数的单行m,n它是网格中的行数和列数.接下来的每一m行都包含n空格分隔的整数,D表示相应单元格中的数字

输出:
对于每个测试用例,在一行中输出一个整数,这是您最后可以得到的最大分数.

约束:
T小于7.
D小于60001.
m且n小于8.

样本输入:

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

样本输出:

5911
10832
0
11493

我尝试过,但我的做法是工作很慢的7×7 grid.I我试图递归访问网格的每一个可能的路径和比较每path.Below的总和是我的代码

#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

我能想到的一种优化是应用Dijkstra 算法。该算法将为您提供特定源节点到所有目标节点的最小（在您的情况下为最大）路径。

在此示例中，第一步是构建图表。

因为您不知道从哪个源节点开始，所以您必须对网格中的每个节点应用 Dijkstra 算法。时间复杂度会比递归方法更好，因为对于特定的源节点，在查找最大路径时，Dijkstra 算法不会遍历所有可能的路径。