7
有一款有趣的遊戲叫做單人遊戲。它在m*n網格上播放。每個網格單元格中都有一個非負整數。您從0開始。您無法輸入其中包含整數0的單元格。您可以在任何想要的單元格開始和結束遊戲（當然，單元格中的數字不能爲0）。在每一步中，您都可以上下左右移動到相鄰的網格單元。您最後可以得到的分數是您路徑上的數字總和。但是最多可以輸入一次單元格。
網格步行高分
該遊戲的目的是讓你的分數儘可能高。
輸入：
輸入的第一行是整數T測試用例的個數。每個測試用例的第一行是一行，包含兩個整數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;
}
請給我建議如何優化這種方法或更好的算法。
由於代碼有效，應該移動到代碼審查？ – tomdemuyt 2012-07-09 19:10:42
@tomdemuyt代碼正在工作，但我正在尋找此代碼中的優化，因爲它對於大型數據集的工作速度非常慢 – archit 2012-07-09 19:16:28
這不是真正的代碼審查，因爲問題不在於如何更好地組織代碼，而是關於高效算法。 – biziclop 2012-07-09 20:17:13