Question

how can i make this program in python?

Captain Øks is on his way to conquer Mosefjell.

He has a map of the area and he is in his camp at the designated place on the map.

The map is divided into cells. For each cell, the height is given.

Captain Øks is not happy, the landscape is full of hills,

and he hates to climb both up and down.

He has hired you to write a program that will find the most comfortable route to Mosefjell.

In other words:

Given a 2-dimensional array A with dimensions M x N,

containing positive integers (A [i, j] represents the height of the map's column i and row j). Write a program that will find a sequence of neighboring cells that starts with a given starting element and ends with a given end element so that the cost is minimal.

For each cell he moves it costs 1.

If he has to move up or down then the height difference is added to the cost.

The difference should be added regardless of whether it goes up or down

(add the absolute value of the difference in height of the two cells).

Neighboring cells must have a common side (eg A [2,2] and A [2,3] are neighbors, while A [2,2] and A [3,3] are not).

The map can be converted to a graph by creating a node for each cell in the map and edges between all neighboring nodes with cost as described above.

The most comfortable way can then be calculated with an algorithm from the lectures.

The map should be loaded from a text file of the following format: Width

Height

x coordinate for Captain Øks camp

y coordinate for Captain Øks camp

x coordinate for Mosefjell

y coordinate for Mosefjell

For each row in the map a line of numbers separated by commas, one number for each column.

A file of this format for the sample map is:

12

8

1

4

10

4

5,5,7,8,9,9,8,8,9,9,7,9

5,6,7,8,7,8,9,8,9,7,8,9

6,6,6,5,6,7,7,8,9,7,8,9

3,3,5,5,5,6,7,7,6,7,8,6

1,1,2,3,7,9,8,8,6,5,5,4

5,5,5,3,7,8,8,7,5,5,5,4

6,7,8,4,4,8,6,6,5,5,3,1

7,7,8,9,4,4,5,5,4,3,1,0

Answer 1

The algorithm that must be used to solve this problem is Floyd Warshall. Since in this problem, you are provided with start cell and a destination cell in a matrix and you are allowed to move to any cell adjacent to your present cell (the cells that are sharing a side). So you can attempt up, down, right and left moves, as soon as you do not move out of the matrix.

For Floyd Warshall, create another matrix using the help of the input matrix. Considering the matrix as a graph, every cell is a node of the graph. Let's first given an integer index to every cell.

mat[i][j] cell can be given index = i*(number of rows) + j;

Like this, an index can be given to every cell.

Now using these indices, we will create a new matrix.

new_matrix[i][j] = difference in height between cell which has an index i and a cell which has an index j. And these both cells will be mandatory adjacent. If the cell are not adjacent, then the new_matrix[i][j] = INFINITY.

Now apply Floyd Warshall on new_matrix and the if 'a' is the index of start cell and 'b' is the index of the destination cell then new_matrix[a][b] will have your answer.

Now, this approach is easy to code but inefficient.

An efficient approach will involve using Dijkstra's algorithm, making use of heaps and priority queues.