Click here to Skip to main content
14,325,701 members
Rate this:
Please Sign up or sign in to vote.
Minimum matrix

You are given an integer matrix A of size N×M. You start on the left upper corner cell (with coordinates (1,1)). You can walk in four directions. You can not visit the same cell twice. You have to visit every cell of matrix A. When you stand on a cell, your maximum value is updated with the value of element on this cell. Initially, the maximum value is equal to A1,1. Your task is to find the path with the minimum number of changes in the maximum value.

SAMPLE INPUT 
3 3
2 1 7
4 1 6
7 4 8

SAMPLE OUTPUT 
1 1
1 2
1 3
2 3
3 3
3 2
2 2
2 1
3 1


What I have tried:

Maximum value initially is equal to 2 and you stood on cell (1, 1). Then you walked on element 1, maximum did not updated. After that you went on element 7, maximum value has become 7. Then you walked on element 6, nothing changed. After that you went on element 8, maximum value has become 8.
Posted
Updated 25-Jun-19 21:35pm
Comments
Stefan_Lang 25-Jun-19 3:05am
   
Hints:
0. The section "Quick answers" is meant to help people fix issues with language syntax, to make a program run, or help people spot an error in a program that already runs, but delivers incorrect results. Where is your program?
1. You are supposed to post those sections of your program that you have trouble with.
2. The section "What I have tried" is supposed to hold variants to that program that you tried in order to get the correct results.
Rate this:
Please Sign up or sign in to vote.

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.
   
Rate this:
Please Sign up or sign in to vote.

Solution 2

Take a look here: Dijsktra's algorithm[^]
   
Comments
Stefan_Lang 26-Jun-19 2:56am
   
It's a variant of the Travelling Salesman Problem with a very special cost function. Unfortunately it's even worse, because to evaluate the cost function you need to know the full path - therefore you can't use Dijkstra's Algorithm.
Maciej Los 26-Jun-19 7:18am
   
Well, i must admit that i disagree. A TSP is used when you have a list of cities and different distances between each pair of cities (cells). In this case the distance between each cell is the same (1 step in any direction). In TSP you have to find the shortest route to the next city and finally return to the initial city. By using Dijkstra’s algorithm you're trying to find the shortest path from source to all vertices in the given graph. The graph is well known, because it is a set of cells in defined area (3x3). All what OP have to do is to find the shortest path to the cell with maximum value. The most important thing is that, that initial position in a graph has been provided - it's a cell (1,1) and the first move can be make in one of directions: right or down.
Cheers
Maciej
Stefan_Lang 27-Jun-19 3:12am
   
Dijkstra's algorithm won't work here: it doesn't care about visiting all cities, and it requires the ability to evaluate a partial path in such a way that it is meaningful for the decision how to construct the full path. Unfortunately the evaluation requires the knowledge of the full path, so this can't be done!

TSP is closer to this problem in that you have to visit all cells, exactly once. That you don't have to return to the start is just a minor variation. The graph you have is a simple grid with connections to the (up to) four neighbouring cells, and the cost for travelling along a specific path can be evaluated once you constructed a valid path.

Having said that, if you can present a working algorithm based on Dijkstra, then you've proven that either this is not a TSP problem, or that P=NP! I doubt that you can, but I'd be happy to be proven wrong. :-)
Maciej Los 27-Jun-19 3:22am
   
Stefan,
Thank you very much for this discussion. I haven never been forced to resolve such of issue. At this moment i do not have enough time to write complete solution for this issue. Maybe, someday...
Cheers,
Maciej
Rate this:
Please Sign up or sign in to vote.

Solution 3

Quote:
Program to find minimum matrix

Yes it is what you have to do !
In this site, we help you to fix your program, but you need to have a program, we don't do your homework for you.
The requirement is typical of challenges sites, so your challenge is to solve the problem, In your case you failed.
Failing to solve the problem with your own work is better than succeed with someone else work.

As far as I can see, brut force is the only way to go. Start simple with a stripped down problem, then elaborate.
- Make a program that will walk every possible path in matrix.
- Make it so you keep track of the current path (to be able to print it).
- add code to get the score of current path.
- add code to remember best path with its score.
   
Comments
Stefan_Lang 26-Jun-19 2:56am
   
"As far as I can see, brut force is the only way to go. "
Yup: it's a variant of the Travelling Salesman Problem with a very special cost function. Unfortunately it's even worse, because to evaluate the cost function you need to know the full path - therefore you can't use Dijkstra's Algorithm.
Rate this:
Please Sign up or sign in to vote.

Solution 4

It's a variant of the Traveling Salesman problem[^] (you have to visit all cells of the matrix) with an unusual cost function. The cost function can only be evaluated once you have a full path. Moreover a full path needs to visit all cells. You migth want to look up implementations of the Visitor Pattern[^] to get an idea on how the code might look like.

To solve the problem you need to enumerate all paths through the Matrix. Since you have no more than 4 directions to go from each cell, and the length of the path must be NxM, the total number of paths starting at cell (1,1) is less than 4^(N*M-1) (4 to the power of (N*M-1), but that's still a lot. It's probably best to avoid those paths that can't be a solution, e. g. by keeping track of which cells you already visited, and not choosing a direction towards a cell that you already visited.

The implementation can be simplified by treating the Matrix as a graph with it's cells as nodes. Each node has links to it's (up to) four neighbors, and maybe it could store index values of it's position in the matrix. For your algorithm, you should also add a link to the next cell in the path you're about to construct in case you visited it:
struct node {
    // links to neighbouring cells of the matrix (may be nullptr):
    node* up;
    node* down;
    node* left;
    node* right;
    // position of the cell within the matrix
    int row;
    int column;
    // next node of the current path
    node* next;
};
struct matrix {
    node* first;
};

To find a path, the most simple solution I can think of is making recursive calls with each cell you add to the path. For each step, you can choose to go in any of the four directions, provided that the pointer is not null (indicating you're at the boundary of the Matrix), and the next pointer of the cell you're going to is a nullptr (otherwise you've already visited it). The recursion is finished when there is no valid direction to go. The path is valid when it has reached a length of NxM.

All in all, that's a lot code to write, but if you follow the outline above it shouldn't be too hard.
   
v2

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100