Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Cheapest path between two elements of an MxN matrix containing nonnegative real numbers..

Aminjoni AbdullozodaAminjoni Abdullozoda Member Posts: 1
  1. Write the program which finds the cheapest path between two elements of an MxN matrix containing nonnegative real numbers. Assume that in each step, you can move only to one of the eight adjacent elements: top-left, top, top-right, left, right, bottom-left, bottom, and bottom- right

ai-1,j-1 ai-1,j ai-1,j+1

ai,j-1 ai,j ai,j+1

ai+1,j-1 ai+1,j ai+1,j+1
( Fig 1)

Fig. 1: All possible transitions from the ai,j element of the matrix A.
The matrix is stored in a text file, where elements belonging to the same row are separated by spaces and matrix rows are separated by semicolons. For instance, the following sequence: 1.2 0.4 0.55 1.5; 3.1 2.82 1.6 8.1; 0.3 3.9 7.1 9.2 corresponds to the 3x4 matrix:
1.2 0.4 0.55 1.5; 3.1 2.82 1.6 8.1; 0.3 3.9 7.1 9.2
When the matrix is loaded into the program, the user can specify indices of the starting and target element assuming that the element indices start from 1, thus, the first element of the matrix is denoted as [1, 1] and the last one as [M, N]. Next, the program displays the list of elements which lie on the path found (including the starting and the target one) and the total cost of the path. The cost is calculated as the sum of element values which lie on the path (excluding the starting and the target element). It should be possible to save the path found into a text file. It is desirable to visualize the path in the program.
As an example, let us consider the element [1, 1] (1.2) as the starting point and the element [3, 3] (7.1) as the target one for the previously given matrix. The program output is:
The cheapest path: [1, 1] (1.2) -> [1, 2] (0.4) -> [2, 3] (1.6) -> [3, 3] (7.1) The total cost: 2.0
Example path visualization:
++--
--+-
--+-

Tagged:
Sign In or Register to comment.