Trick-or-Treat (Halloween C programming)

[galaxy_twirl]

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

NIL.

The Attempt at a Solution

#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

 

[Borek]

Without even trying to analyze the code: try to run you algorithm by hand first, and then compare what the program really does running it under debugger. That's a method that always help find where things go not as expected.

 

[galaxy_twirl]

Without even trying to analyze the code: try to run you algorithm by hand first, and then compare what the program really does running it under debugger. That's a method that always help find where things go not as expected.

Hi Borek. Ah alright~ I think I should try to trace the program again. I guess I was frustrated after spending 2 hours with my teacher guiding me to work this problem out and another 30 mins trying to debug the program as vim threw out a paragraph of errors at me. I should be more patient. Sorry. ><

Just wondering, do I trace the program from the start to the end? This is because I suspect the problem lies with the function maxtreats at the back.

Oh ya. Just wondering, wit regards to the debugger, is it called the gdb in vim?

Thanks for your advice! :)

 

[Borek]

is it called the gdb in vim?

What OS do you use? vim is just a text editor, gdb is a debugger, but it is not a part of vim. I must admit I have never used gdb (being a Visual Studio user).

 

[galaxy_twirl]

I use Windows 7. :) I see. I think gdb is an extension built into the vim I am using. Wow. So does that mean Visual Studio has a built in debugger? :D

 

[Borek]

does that mean Visual Studio has a built in debugger?

Visual Studio is an integrated development environment (IDE), so it has everything combined. Note it is a commercial product (and not a cheap one), but chances are free entry level version (Visual Studio Express) has everything you need. Visit Microsoft pages to check details.

 

[galaxy_twirl]

Visual Studio is an integrated development environment (IDE), so it has everything combined. Note it is a commercial product (and not a cheap one), but chances are free entry level version (Visual Studio Express) has everything you need. Visit Microsoft pages to check details.

I see. :) Thank you for your recommendation! I will try to debug the code later if I have to do my Math homework now.. :( I will update here if I run into any more problems. :)