How to find the number of path from source to destination which adds upto to a given sum k in a 2d matrix?

Question

1.00/5 (2 votes)

See more:

In NxN matrix containing numbers and block 'x'.find the number of path from the source 's' to destination 'd' which adds upto given sum 'k'. Use Dynamic programming to solve this.Move in down ,right and diagonal direction.

input:
--------------
k = 3

s 1 1
1 x 1
1 1 d

output = 2
--------------
k = 5

e 1 1 1

1 1 1 1

1 1 1 1

1 1 1 s

output = 20
-------------

k = 7

e 2 3

2 x 2

1 2 s

output = 1
-------------

What I have tried:

I have tried using recursion, as it will take more time complexity.

C++

int countpath(char a[][100], int i,int j,int val)
{
    if (
        (
            (i == n-1) &&
            j == (n-1)
        )
        &&
        (
            (a[n-1][n-1] == k) ||
            (a[n-2][n-2] == k) ||
            (a[n-1][n-2] == k) ||
            (a[n-2][n-1] == k)
        )
    )
    {
        return 1;
    }
    else 
        return 0;

    a[0][0] = 0;

    if (
        i = 0 &&
        j < n-1 &&
        a[i][j+1] != 'x'
    )
        return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');

    if (
        j = 0 &&
        i < n-1 &&
        a[i+1][j] != 'x'
    )
        return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');

    if ( a[i][j] != 'x' )
        return countpath(a, i+1,j+1, (a[i+1][j+1]+a[i+1][j]+a[i][j+1])-'0');

}

Posted 1-Jun-19 18:10pm

User 14444878

Updated 3-Jun-19 0:21am

Stefan_Lang

v3

Add a Solution

Comments

Stefan_Lang 3-Jun-19 5:13am

"find the number of path"
What does "path" mean in this context? What does "number of path" mean'

Also: why do some of the inputs not contain x, some do not contain d, and some contain e which is not explained in the question?

If we're supposed to help you on a task, you'd better take more care of specifiying the task given to you accurately.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Answer 1 · 2019-06-03T00:22:00

Your function countpath shows a number of issues. I'll point out a couple that are obvious to me and suggest you fix them before continuing - maybe afterwards you can continue on your own, otherwise you can always come back here and ask:

1. Your first if statement will return a value (1 or 0) on both branches. Therefore the code after that if-else block will never be executed. I suspect that the else case should not always return 0: you're probably missing another if?

2. The second and third if statement contain assignments (i = 0 and j = 0 respectively) . Did you mean to make comparisons here?

3. This is a tricky one: You're passing a matrix a into the function, defining it as having 100 columns, although the true size (NxN) is probably much smaller. With that definition, a[1][0] will access the address [a+100], which may be outside of the allocated memory space for the matrix a, if it was defined as 10x10 or smaller! You didn't ahow your calling function, which should declare and allocate a. If you defined it as 100x100, independent of N, it's probably ok. Otherwise you'll need to fix that.

4. And a less obvious one: Your code appears to be testing whether you can continue in a specific direction, and, if so, calculate the number of paths for that direction recursively. However, you're forgetting that after this recursion, you should also test the other directions too, and add those numbers to the total. Instead you immediately return with the number you obtained from going into that one direction, ignoring other options. Which means you'll never be able to find more than one path...

OriginalGriff · Answer 2 · 2019-06-01T19:48:00

Solution 1

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

Posted 1-Jun-19 19:48pm

OriginalGriff

Comments

[no name] 2-Jun-19 3:46am

I have written the below piece of function ,but its not working

int countpath(char a[][100], int i,int j,int val)
{
if(((i == n-1) && j == (n-1) ) && ((a[n-1][n-1] == k) || (a[n-2][n-2] == k) || (a[n-1][n-2] == k) || (a[n-2][n-1] == k)))
{
return 1;
}
else
return 0;

a[0][0] = 0;

if(i = 0 && j < n-1 && a[i][j+1] != 'x')
return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');

if(j = 0 && i < n-1 && a[i+1][j] != 'x')
return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');

if(a[i][j] != 'x')
return countpath(a, i+1,j+1, (a[i+1][j+1]+a[i+1][j]+a[i][j+1])-'0');

}

Patrice T 2-Jun-19 3:48am

Use Improve question to update your question.
So that everyone can pay attention to this information.

OriginalGriff 2-Jun-19 3:53am

"It's not working" is one of the most useless problem descriptions we get: it tells us absolutely nothing about the problem. We don't know if you get an error message, or the wrong data, or even that that code compiles successfully!
Remember that we can't see your screen, access your HDD, or read your mind - we only get exactly what you type to work with.
So tell us what happens when you run that code, what you expected to happen, how you checked what happened. Help us to help you!
Use the "Improve question" widget to edit your question and provide better information.

Stefan_Lang 3-Jun-19 5:44am

This function will always return 1 or 0 and never reach the code after your first if ... else ...

This code will clearly _not_ return a value that is too high, so it's not the code that you were talking about initially.

Besides, you should add explanations on the function parameters, especially what is the purpose of i and j. We might guess it from their use in your code, but if they are part of the problem, we might guess wrong.

Please use the [Improve question] button below your question to add the real, complete code to your question and explanations, so everyone can see what you're working on.

[no name] 2-Jun-19 3:58am

In the above piece of code ,it was getting compiled sucessfully, and the ouput printed is a higer value than what is expected

OriginalGriff 2-Jun-19 4:56am

This has "long day" written all over it...
So ... you wrote some code, put some data that we haven't got into it, and if gave you a "higher value".
That's helpful. Not a lot, but it's a start.
Initially, you went for a drive, and broke down in the middle of nowhere. You rang the garage and said "It broke" and put the phone down. Now you are waiting for the garage to turn up with the right bits for your car without knowing which car it is, what happened to it, who you are, or any idea of where it might be.

Now you have revised it and the call went "Joe's Garage, how can we help?" "It broke. It's a Fiat."
I suspect you are going to be sitting by the road for a very long time before the garage arrive with the new radiator, or tire: They have to search the entire country for you, and guess what part broke yet.

We are the same: feed us sod all, we can do sod all.
So tell us what you did yo get the results, what happened, what you have done to find out why. What data did you feed it? How did you check the data was correct? What did the debugger show you when you used that to look at what was going on? What path through the code and data did it take when you ran it?

Stefan_Lang 3-Jun-19 5:59am

I've added this code block to your question and reformatted it for readability. I did not add or remove anything but whitespace.

Patrice T · Answer 3 · 2019-06-01T20:41:00

Quote:
How to find the number of path from source to destination which adds upto to a given sum k in a 2d matrix?

This look like some homework, but your main effort is pasting the requirement.
What is the question?

Quote:
Use Dynamic programming to solve this.

You are given hint about how to do.

We are not doing your homework, if you want help, you need to show your work and explain problem.

To get you started, you can start with a brute force approach (trying every path 1 by 1), then refine.
[Update]

Quote:
In the above piece of code ,it was getting compiled sucessfully, and the ouput printed is a higer value than what is expected

How is your code handle letters that are not 'x' ?

[Update]
Looks like your code never goes beyond this point

C++

int countpath(char a[][100], int i,int j,int val)
{
    if (
        (
            (i == n-1) &&
            j == (n-1)
        )
        &&
        (
            (a[n-1][n-1] == k) ||
            (a[n-2][n-2] == k) ||
            (a[n-1][n-2] == k) ||
            (a[n-2][n-1] == k)
        )
    )
    {
        return 1;
    }
    else 
        return 0;
// code beyond this point is never executed
    a[0][0] = 0;

    if (
        i = 0 &&
        j < n-1 &&
        a[i][j+1] != 'x'
    )
        return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');

    if (
        j = 0 &&
        i < n-1 &&
        a[i+1][j] != 'x'
    )
        return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');

    if ( a[i][j] != 'x' )
        return countpath(a, i+1,j+1, (a[i+1][j+1]+a[i+1][j]+a[i][j+1])-'0');

}

Looks like you should learn the debugger.

How to find the number of path from source to destination which adds upto to a given sum k in a 2d matrix?

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0