Поиск максимума пути в 2D-массиве

Question

Хэллоуин за углом, и пришло время для хитрости или лечения. Вы находитесь в верхнем левом углу карты города n-by-n и отправляетесь на вечеринку на Хэллоуин, расположенную в нижнем правом углу. Во время вашей поездки вы решили посетить минимальное количество домов, чтобы угоститься. У вас есть карта города с информацией о количестве угощений (≥ 0), доступных в каждом месте. Например, карта города для n = 3 показана ниже.

Чтобы получить максимум удовольствия, вы будете исходить из дома (6), а затем на восток до (8), а затем на юг на (5), затем на юг (9), затем на восток (10) и заканчивается на стороне.

Таким образом, количество обработок равно 6 + 8 + 5 + 9 + 10 = 38.

Обратите внимание, что для посещения минимального количества домов вам необходимо либо отправиться на восток, либо на юг из одного дома в другой, пока вы не придете на вечеринку. Чтобы получить максимальные удовольствия, отслеживайте текущий максимум при посещении каждого дома.

6, 14, 14 + 2 = 16

10, 5 + макс (10,14) = 19

3 + 10 = 13

Таким образом, программа должна быть выбирая максимальное значение для добавления, скажем, для 10 и 14, я хочу добавить 14. Но у меня проблемы с этим использованием для циклов. Кто-нибудь может помочь?

---

1 #include <stdio.h> 
 
    2 
 
    3 #define SIZE 10 
 
    4 
 
    5 int pathmax(int map[][SIZE], int n); 
 
    6 void read(int map[][SIZE], int n); 
 
    7 int max(int x, int y); 
 
    8 
 
    9 int main(void) 
 
10 { 
 
11 int map[SIZE][SIZE], n; 
 
12 
 
13 printf("Enter n: "); 
 
14 scanf("%d", &n); 
 
15 
 
16 read(map,n); 
 
17 
 
18 printf("Maximum: %d\n", pathmax(map,n)); 
 
19 
 
20 return 0; 
 
21 } 
 
22 
 
23 int max(int x, int y) 
 
24 { 
 
25 if (x > y) 
 
26  return x; 
 
27 else 
 
28  return y; 
 
29 } 
 
30 
 
31 int pathmax(int map[][SIZE], int n) 
 
32 { 
 
33 int k, i, j; 
 
34 
 
35 for (k = 1; k < 2*n-1; k++) 
 
36  for (i = 0; i < n; i++) 
 
37   for (j = 0; j < n; j++) 
 
        if(i+j==k) 
 
        { 
 
        if (i==0) 
 
         map[i][j] += map[i][j-1]; 
 
        else if (j == 0) 
 
         map[i][j] += map[i-1][j]; 
 
        else 
 
         map[i][j] += max(map[i-1][j], map[i][j-1]; 
 
           } 
 
           
 
           } 
 
          

Answer 1

рекурсивного решение, будет учитель поверить, что ты написал?

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define MAXTREAT 10 
#define GRID  3 

int map [GRID][GRID]; 
int maxtreats; 

void explore(int x, int y, int treats) 
{ 
    treats += map [y][x]; 
    if (x == GRID-1 && y == GRID-1) { // reached bottom right? 
     if (treats > maxtreats)   // check result 
      maxtreats = treats;   // finish recursion 
    } else {       // recurse 
     if (x+1 < GRID) 
      explore (x+1, y, treats); // go east 
     if (y+1 < GRID) 
      explore (x, y+1, treats); // go south 
    } 
} 

int main() 
{ 
    int x, y; 
    srand ((unsigned int)time(NULL)); // seed random num gen 
    for (x=0; x<GRID; x++) {   // set up random map 
     for (y=0; y<GRID; y++) { 
      map[y][x] = 1 + rand() % MAXTREAT; 
      printf ("%4d", map[y][x]); 
     } 
     printf ("\n"); 
    } 
    explore (0, 0, 0); 
    printf ("Max treats %d\n", maxtreats); 
    return 0; 
}