- #1

galaxy_twirl

- 137

- 1

## Homework Statement

**Trick Or Treat**

Halloween is round the corner and it's time for trick-or-treating. You reside at the top left corner of a n-by-n town map and heading to the halloween party located at the bottom right corner. While on your trip, you decide to visit a minimal number of houses to get treats. You have a map of town with information of the amount of treats (≥ 0) available at each location. As an example, the town map for n=3 is shown below.

6 8 2

4 5 1

3 9 10

To get the maximum treats, you will start from home (6), then head east to (8), then south to (5), then south to (9), then east to (10) and end up at the party.

So the number of treats is 6+8+5+9+10=38.

Notice that to visit a minimal number of houses, it necessitates that you either travel east or south from one house to the next until you arrive at the party. To obtain the maximum treats, track the current maximum as you visit each home. Example:

The final value obtained at the party will be the maximum amount of treats.

Write a program that reads n followed by the n-by-n town map and determines the maximum amount of treats. Assume that the town map does not exceed 10-by-10.

**Sample Runs**

The following are sample runs of the program. User input is underlined. Ensure that the last line of output is followed by a newline character.

Sample run #1:

Enter n: 3

6 8 2

4 5 1

3 9 10

Maximum: 38

Sample run #2:

Enter n: 3

1 3 4

2 5 8

6 7 9

Maximum: 26

2. Homework Equations

2. Homework Equations

NIL.

## The Attempt at a Solution

Code:

```
#include <stdio.h>
#define ROW 11
#define COL 11
void readarr1(int arr1[][COL], int n);
void directmaxtoprow(int arr1[][COL],int arr2[][COL], int n);
void directmaxleftmostCOL(int arr1[][COL], int arr2[][COL], int n);
void maxtreats(int arr1[][COL], int arr2[][COL],int n);
int main(void)
{
int n=0;
int arr1[ROW][COL]={{0}};
int arr2[ROW][COL]={{0}};
scanf("%d", &n); //Size of array (or map)
readarr1(arr1,n);
directmaxtoprow(arr1,arr2,n);
arr2[0][0] = arr1[0][0];
directmaxleftmostCOL (arr1,arr2,n);
arr2[0][0] = arr1[0][0];
maxtreats(arr1, arr2, n);
printf("%d\n", arr2[n-1][n-1]);
return 0;
}
void readarr1(int arr1[][COL], int n)
{
int i=0, j=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&(arr1[i][j]));
}
}
return;
}
void directmaxtoprow(int arr1[][COL],int arr2[][COL], int n)
{
int j=0;
for(j=1;j<n;j++)
{
arr2[0][j] = arr2[0][j-1]+arr1[0][j];
}
return;
}
void directmaxleftmostCOL(int arr1[][COL], int arr2[][COL], int n)
{
int i=0;
for(i=1;i<n;i++)
{
arr2[i][0]=arr2[i-1][0]+arr1[i][0];
}
return;
}
void maxtreats(int arr1[][COL], int arr2[][COL], int n)
{
int i=0, j=0;
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(arr2[i-1][j]>arr2[i][j-1])
{
arr2[i][j] = arr2[i-1][j] + arr1[i][j];
}
else
{
arr2[i][j] = arr2[i][j-1] + arr1[i][j];
}
}
}
return;
}
```

I have a problem with the above code but I can't seem to find the problem. When I entered Sample Run #1, the output was 34 instead of the desired 38. May I have some guidance on what is wrong with my above code?

Thanks! :D