2D array task

[mikesr]

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.

[Clinton Portis]

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--;          
     }
}

[Clinton Portis]

//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--;          
     }

[mikesr]

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!

[mikesr]

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.

[Agni]

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 :)

[mrnutty]

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

[mikesr]

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]

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

[mikesr]

#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;
}

[Agni]

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?

[mikesr]

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..