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.

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.