c - 查找二维数组中的路径最大值

Question

万圣节即将来临，又到了“不给糖就捣蛋”的时间。您居住在 n×n 城镇 map 的左上角，并前往位于右下角的万圣节派对。在旅途中，您决定参观最少数量的房屋以获得奖励。您有一张城镇 map ，其中包含每个位置提供的零食数量 (≥ 0) 的信息。例如，n=3 的城镇 map 如下所示。

6 8 2

4 5 1

3 9 10

要获得最多的奖励，您将从家 (6) 开始，然后向东到 (8)，然后向南到 (5)，然后向南到 (9)，然后向东到 (10)，最后到达聚会。

所以零食的数量是6+8+5+9+10=38。

请注意，要参观最少数量的房屋，您需要从一栋房屋向东或向南行驶到另一栋房屋，直到到达聚会地点。要获得最大奖励，请在访问每个家庭时跟踪当前的最大奖励。

6, 14, 2+14=16

10, 5+最大(10,14)=19

3+10=13

所以程序需要选择要添加的最大值，比如说 10 和 14，我会选择添加 14。但是我在使用 for 循环时遇到了麻烦。有人可以帮忙吗？

<小时/>

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;
}