# OOP class

Page 1 of 1

## 7 Replies - 2527 Views - Last Post: 25 January 2006 - 07:20 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=14342&amp;s=b71d6f9d33075003abea7d1df60cab59&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 henry

Reputation: 0
• Posts: 96
• Joined: 03-January 06

# OOP class

Posted 23 January 2006 - 02:29 AM

This is the question
But the question have something worry
I don't understand the diagram given
how the line go?
This is the Question....
Who have solve this question before or other
can you explain it in more detail
thank you

#### Attached File(s)

Is This A Good Question/Topic? 0

## Replies To: OOP class

### #2 born2c0de

• printf("I'm a %XR",195936478);

Reputation: 187
• Posts: 4,673
• Joined: 26-November 04

## Re: OOP class

Posted 23 January 2006 - 04:48 AM

The Question is rather simple.
Create a matrix class and find out the shortest path (shortest sum of the weights) from the (1,1) to (last row,last column)
Allow the User to input data for the matrix first and the calculate the shortest path.

This is a good problem so I wont break the solution to you.
I'll give you a hint though.
For example(using the illustrations from the DOC File): In a 5x5 Matrix, no matter which direction you go...you will always take 4 steps downwards and 5 steps to the right.
A Diagonal Step for this example can be represented as 1 step to the right + 1 step downwards.

All the Best.
If you have any problems while coding...You can ask freely.

### #3 henry

Reputation: 0
• Posts: 96
• Joined: 03-January 06

## Re: OOP class

Posted 23 January 2006 - 08:25 PM

I still not get it
Can you explain how the road is going on at the diagram?
How it is done?
Thank you

• g+ + -o drink whiskey.cpp

Reputation: 250
• Posts: 13,507
• Joined: 12-July 02

## Re: OOP class

Posted 23 January 2006 - 08:30 PM

Henry, I hate to ask, but have you gone through the assignment? Is there a particular concept which you do not understand? Is it matrices in general that you would like some help with, or the concept of determining the least weight?

The best course of action may be to populate a matrix with the values given in the file, and then take a few sample traversals to add up the values. You can then experiment with checking all the values that are eleigible from the current value from which you sit...then move onto taking end values into consideration, etc...

Remeber that the matrix wraps (last row can move up into the first row), and that you can move up a row as well as down a row (born2code may have given the impression that moves must always be down and to the right...you can go up as well, but always to the right).

### #5 henry

Reputation: 0
• Posts: 96
• Joined: 03-January 06

## Re: OOP class

Posted 24 January 2006 - 12:00 AM

any hint
What to use?
Give me a bit only..
Thank
Smile........
I don't want answer but hint ok

### #6 born2c0de

• printf("I'm a %XR",195936478);

Reputation: 187
• Posts: 4,673
• Joined: 26-November 04

## Re: OOP class

Posted 25 January 2006 - 04:49 AM

Amadeus, on 24 Jan, 2006 - 09:57 AM, said:

(born2code may have given the impression that moves must always be down and to the right)

Oops....Thanks for pointing that out Amadeus.
I must have missed it.

### #7 1lacca

• code.rascal

Reputation: 44
• Posts: 3,822
• Joined: 11-August 05

## Re: OOP class

Posted 25 January 2006 - 07:18 AM

First of all, the assignment has a bug: it starts with specifying a matrix of size NxN and then it talks about sizes of 5x6 and so on

Anyway, you could go along and implementDijkstra's algorythm if no negative values shall be present in the matrix- as this is the fastest way to solve this problem.
However note that it takes a graph given by its adjacency mtrix, and that is different from the matrix you are given! So you must convert it first. If the given matriy is NxM the converted will be (N*M)x(N*M) - quite large, but sparse, so you might look for an edge-list implementation, but I'm not sure if it worth the effort. Another hint: this way you should have start hte algorythm as many times as the number of rows, as the path can start anywhere in the first column, but if you add a new edge to the graph that is connected with all of the cells of the first column, you can finish with one run ( although the converted matrix will be (N*M+1)x(N*M+1).
Conversion should be easy, each cell in the old matrix gives value to 3 cells in the converted one.

### #8 1lacca

• code.rascal

Reputation: 44
• Posts: 3,822
• Joined: 11-August 05

## Re: OOP class

Posted 25 January 2006 - 07:20 AM

And yes, I have given you a link on purpose written in Java, so that it can be used as pseudo code, but it doesn't destroy the challenge