Hello!
I am new one here. Firstly I would like to say that I'm really poor in english, so be patient with me..

In the school we had a new task. So let me explain: we have a 2d array with numbers.. like this:
0 1 2 4 5 6
1 3 4 5 6 7
3 4 7 8 9 4
9 8 7 6 5 2
now, we give the target. For example index 2 4. (in this case is number 9 on that place) . Then I need to find cheaper way from index 0 0 to target on index 2 4 (always for one step) ... So in this case the program should go like that: 0, 1, 2, 4, 5, 9 (if we look numbers), or indexes( 0 0, 0 1, 0 2, 1 3, and finally 2 4). Then we need to find cheaper way back from target on index 2 4 to index 0 0 (on different way(we can not use the same places we had before)).. So the way back should be like that: 9, 8, 4, 3, 0(if we look numbers), or 2 4, 2 3, 1 2, 1 1 and 0 0(if we look indexes).

Any help will be appreciated.

ps: Like I sad, we speak different language here.. Because of that, I'm terrible with english language (I understand it very well, but I can not write it, because we have different expression here). I apologize for this.

Recommended Answers

All 11 Replies

Here is just one possible solution to the first part of the problem, there are probably much better loop(s) you can come up with but I am lazy. It is pretty much self explanitory. You can give the second part of your problem a try. Let me know if you have any questions.

int x = 3;
for(int row=0, col=0; row<6; col++)
{
     
     //Account for the offset required for the last loop iteration in order to display the 2d_array[2][4] special case.
     if(row == 3)

          col++;

     
     //If all array counters jive, then display data, else adjust array counters to get the results we want.
     else if(row > x)

          cout << 2d_array[row][col];  

     //Make row-to-row transitions
     else 
     {
          x += (x-1);
          row++;
          col--;          
     }
}
//This
for(int row=0, col=0; row<6; col++)
//Should be this
for(int row=0, col=0; col<5; col++)
//Make row-to-row transitions
     else 
     {
          x += (x-1);
         //This
          row --;
          //Might have to be this
          row -= 2;
          col--;          
     }

Forgive me, Clinton Portis. We had a misunderstanding.. I didn't mean for the same 2d array.. I typed it as an example.. The 2d array can be changeable by numbers and size.

Anyway, thank you for helping me! I really appreciate it!

I'm going to make this much easier to understand..
example 2d array:
1 8 3 4
1 9 1 6
1 1 1 5

begininig is always on array[0][0]
target(for example): array[1][2]
So we look cheapest way from 0 0 to 1 2.. In that case: 1+ 1 +1 + 1 + 1 +1 = 6 (or indexes: 0 0, 1 0, 2 0, 2 1, 2 2, 1 2)
So if I summarize: we need to find minimum sum to the target..

another example:
0 2 3 4 5 8
4 5 6 8 4 2
8 9 4 3 2 1
9 8 7 3 2 7
target(for example): array[2][2]
so the minimum sum is: 0 + 5 + 4=9 (or indexes: 0 0, 1 1, 2 2)

I hope you understand it better.

This looks like a shortest path problem. You can consider each element to be a vertex in a graph (so you have 12 vertices for the first matrix) and only connected to vertices directly to right-left-top-bottom of itself in the vertex. The weight of each edge is the value in the matrix. and then you can apply a standard algorithm like djikstra. this is the link to it on wikipedia and will give you a pseudocode for it.
Dijkstra's shortest path

i hope i've understood the problem correctly. if not dijkstra is still not a bad algorithm to learn :)

All you need to know is the slope formula, and how to create a mx+b line.
Do you know how to do that?

Agni: Thank you! I've been trying all day to modify for my task. It's just not that simple, I guess.

firstPerson: Would you mind telling me more about solution?

Agni: Thank you! I've been trying all day to modify for my task. It's just not that simple, I guess.

firstPerson: Would you mind telling me more about solution?

post your code, whatever you have done. Lets take a look

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <queue>
using namespace std;

const int SIZE = 5; //number of nodes
int graph[SIZE][SIZE];//the graph itself
int d[SIZE]; //distances from the source to each node
int pi[SIZE];//contains the predecessor node for each node
vector<int> s;//list of nodes which were already visited
vector<int> vs;//list of nodes which were not visited yet

void sort(vector<int>* vec) {
     //sorts the vector of nodes according to 
     //distances from the source to each node
     for (unsigned int i = 0; i < vec->size(); i++)
        for (unsigned int j = i; j < vec->size(); j++)
            if (d[vec->at(i)] > d[vec->at(j)]) {
                              int temp = vec->at(i);
                              vec->at(i) = vec->at(j);
                              vec->at(j) = temp;
            }
}
void relax(vector<int>* vec, int u) {
     //updates the distances from the source to each node
     //and the predecessor for each node
     for (unsigned int i = 0; i < vec->size(); i++) {
         int vi = vec->at(i);
         if (graph[u][vi] == SHRT_MAX)
            continue;
         if (d[vi] > d[u] + graph[u][vi]) {
            d[vi] = d[u] + graph[u][vi];
            pi[vi] = u;
         }
     }
}

void printShortestPathTo(int v) {
     //this prints the vector of predecessors
     //for the requested node (v)
     cout << "Distance to " << v << " is " << d[v] << endl;
     cout << "Shortest path: ";
     int x = pi[v];
     while (x != -1) {
           cout << x << "<-";
           x = pi[x];
     }
     cout << endl << endl;
}

int main() {
    int g;    
    //initialize all the costs in the graph
    cout<<"Insert 5x5 matrix:\n";
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < SIZE; j++)
            cin>>graph[i][j];
    
    for (int i = 0; i < SIZE; i++) {
        vs.push_back(i);//initialize all the variables
        d[i] = SHRT_MAX;//all distances to infinite
        pi[i] = -1;//nodes have no predecesors 
    }
    d[0] = 0; //the distance of the source is 0
    sort(&vs); //we sort the nodes according to the distance
    
    while (vs.size() > 0) {
           int x = vs.front();//take the node with the shortest distance
           for (unsigned int i = 0; i < vs.size() - 1; i++) {
               vs.at(i) = vs.at(i + 1);
           }        
           vs.pop_back();
           s.push_back(x);//mark it as visited 
           relax(&vs, x);//update the distances
           sort(&vs); //sort the nodes according to the new distances
    }
    cout<<"Insert target node: ";
    cin>>g;
    printShortestPathTo(g);
    system("pause");
    return 0;
}

It's quite sad that you have flicked somebody else's code, and without acknowledement :( .. Source. What's the whole point, you can get the implemetation anywhere, easily, why waste our time?

Yes it's true, I copied the code.. I have my own translated in my language and it's very difficult to translate all in english.
Anyway, is the same algorithm. So I thought it would be easier like that.
Well, I made a mistake..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.