Istnieje interesująca gra o nazwie jedna osoba. Gra się na siatce m*n. W każdej komórce siatki znajduje się nieujemna liczba całkowita. Zaczynasz z wynikiem 0. Nie możesz wprowadzić komórki zawierającej liczbę całkowitą 0. Możesz rozpocząć i zakończyć grę w dowolnej komórce (oczywiście numer w komórce nie może być 0). Na każdym kroku możesz iść w górę, w dół, w lewo i w prawo do sąsiedniej komórki siatki. Wynik, który można uzyskać w końcu, jest sumą liczb na twojej ścieżce. Ale możesz wpisać każdą komórkę co najwyżej raz.
Wysoki wynik w siatce spacerowej
Celem gry jest uzyskanie jak najwyższego wyniku.
Wejście:
Pierwszą linią wejściową jest liczba całkowita T liczba przypadków testowych. Pierwszy wiersz każdego przypadku testowego to pojedyncza linia zawierająca 2 liczby całkowite m i n, która jest liczbą wierszy i kolumn w siatce. Każdy z kolejnych z m wierszy zawiera n oddzielonych spacjami liczb całkowitych D wskazaniem liczby w odpowiedniej komórce
wyjściowa:
dla każdego wyjścia przypadków testowych liczbę całkowitą w jednej linii, która jest maksymalny wynik można uzyskać w końcu.
Ograniczenia:
T jest mniejsza niż 7.
D jest mniejsza niż 60001.
m i n mniej niż 8.
próbki wejściowe:
4
1 1
5911
1 2
10832 0
1 1
0
4 1
0
8955
0
11493
Sample Wyjście:
5911
10832
0
11493
próbowałem go, ale moje podejście działa bardzo wolno na 7x7 grid.I próbuję przejść każdą możliwą ścieżkę siatki rekurencyjnie i porównując sumę wszystkich path.Below jest mój kod
#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;
}
Proszę zasugerować, jak zoptymalizować to podejście lub lepszy algorytm.
Powinny zostać przeniesione do przeglądu kodu, ponieważ kod działa? – tomdemuyt
Kod @tomdemuyt działa, ale szukam optymalizacji w tym kodzie, ponieważ działa bardzo wolno dla dużych zestawów danych – archit
To naprawdę nie jest przegląd kodu, ponieważ nie chodzi o to, jak lepiej zorganizować kod, ale o sprawny algorytm . – biziclop