一人遊びという面白いゲームがあります。m*nグリッド上でプレイされます。各グリッド セルには負でない整数があります。You start with a score of 0. 整数 0 を含むセルを入力することはできません。任意のセルでゲームを開始および終了できます (もちろん、セル内の数字が 0 になることはありません)。各ステップで、隣接するグリッド セルに上下左右に移動できます。最終的に獲得できるスコアは、パス上の数字の合計です。ただし、各セルに入力できるのは最大 1 回です。
ゲームの目的は、できるだけ高いスコアを獲得することです。
入力: 入力の最初の行は、テスト ケースの数の
整数です。各テスト ケースの最初の行は、グリッド内の行と列の数である2 つの整数をT含む 1行です。次の各行には、対応するセルの数値を示すスペースで区切られた整数が含まれますmnmnD
出力:
各テスト ケースに対して、最終的に取得できる最大スコアである 1 行の整数を出力します。
制約:
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
私はそれを試しましたが、私のアプローチは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;
}
このアプローチまたはより良いアルゴリズムを最適化する方法を教えてください。