1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trick-or-Treat (Halloween C programming)

  1. Nov 11, 2014 #1
    1. The problem statement, all variables and given/known data

    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:

    ngdi50.jpg

    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. Relevant equations


    NIL.

    3. The attempt at a solution

    Code (Text):

    #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
     
  2. jcsd
  3. Nov 11, 2014 #2

    Borek

    User Avatar

    Staff: Mentor

    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.
     
  4. Nov 11, 2014 #3
    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! :)
     
  5. Nov 11, 2014 #4

    Borek

    User Avatar

    Staff: Mentor

    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).
     
  6. Nov 11, 2014 #5
    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
     
  7. Nov 11, 2014 #6

    Borek

    User Avatar

    Staff: Mentor

    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.
     
  8. Nov 11, 2014 #7
    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. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Trick-or-Treat (Halloween C programming)
  1. Program in C (Replies: 1)

  2. C++ Program (Replies: 17)

Loading...