# Create a matrix with all elements having the value of the shortest path to a given position

You're given the number of rows and columns and the indices for the reference point. Reference point is = 0.
i.e:
3 4 3 3
output:
4 3 2 3
3 2 1 2
2 1 0 1

I managed to solve the problem using the easiest solution there is. I calculated the elements from the same column, and then using 2 for loops I used for every single element the already calculated value from the respective row as a new reference point. I was stuck on this at first because I tried to come up with a formula so I asked on stackoverflow, and told me to submit a code, any solution.. so I came up with this:

#include <iostream>
using namespace std;
int main()
{
int v[501][501], i, j, m, n, o, p;
cin >> m >> n >> o >> p;
for (i = o; i >= 1; i--)
v[i][p] = o - i;
for(i = o;i <= m; i++)
v[i][p] = i - o;
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++){
if(j < p)
v[i][j] = -j + p + v[i][p];
else if(j > p)
v[i][j] = j - p + v[i][p];
}
for(i = 1 ; i <= m; i++){
for(j = 1; j <= n; j++)
cout << v[i][j] << " ";
cout << '\n';
}
}


How can I improve it?

Some suggestions:

• Use variable names that tells the reader what they are.
• Dont do using namespace std; in the global namespace.
• Always check that <stream> >> variable actually worked or else your program will run with uninitialized variables and cause undefined behaviour if they are read.
• Use an unsigned type when dealing with subscripting.
• If you use a hardcoded array size, check that the values entered by the user actually fits in the array.
• Don't use a hardcoded array size when the required size is unknown at compile time.
• Use 0-based arrays instead of 1-based.

When it comes to the actual algorithm, it seems like that the shortest path from any point is
abs(point.row - reference.row) + abs(point.column - reference.column)
which would give code like this:

#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>

// a helper type to keep the reference point
class point_t {
public:
point_t() : point_t(0, 0) {}
point_t(unsigned Row, unsigned Col) : row(Row), col(Col) {}

// a function to calculate the distance to another point
unsigned distance_to(const point_t& p) const {
return static_cast<unsigned>(
std::abs(static_cast<int>(row) - static_cast<int>(p.row)) +
std::abs(static_cast<int>(col) - static_cast<int>(p.col)));
}

// reading the point from an istream
friend std::istream& operator>>(std::istream& is, point_t& p) {
return is >> p.row >> p.col;
}

private:
unsigned row;
unsigned col;
};

int main() {
unsigned rows;
unsigned cols;
point_t ref;

if(std::cin >> rows >> cols >> ref) {
// check that it's not too big
if(rows > std::numeric_limits<int>::max() ||
cols > std::numeric_limits<int>::max()) {
std::cerr << "matrix too big\n";
return 1;
}

// create a 2D vector
std::vector<std::vector<unsigned>> mat(rows, std::vector<unsigned>(cols, 0));

// fill the matrix
for(unsigned row = 0; row < rows; ++row) {
for(unsigned col = 0; col < cols; ++col) {
// use the distance_to function
mat[row][col] = ref.distance_to(point_t(row, col));
}
}

// print the result
for(const auto& row : mat) {
for(auto col : row) std::cout << col;
std::cout << '\n';
}
}
}


Input (with a 0-based reference point)

3 4 2 2


Output

4323
3212
2101


• Thanks a lot for the reply, I am currently learning from a course made by an ex-google intern and apart from iostream math.h fstream, no other library was presented yet and I'm already 70% done with the C++ course.. A lot of the syntax used I don't understand, is it OOP? Can you please tell me a good source to learn C++ from, it's really a shame that I don't understand your code and it's written very well, I wanna have a deep understanding of your solution. – nultype Apr 3 at 13:01
• I'm currently on a train without my computer, but I'll see what I can do Tonight or Tomorrow. – Ted Lyngmo Apr 3 at 13:04
• enjoy you trip, Ted!! – nultype Apr 3 at 13:08
• I am unexperienced at Code Review so I don't know if this is ok or not. My answer is way too long to be in a comment. Too long by over 1KiB as it happens. Can you split the question(s) up and post them as separate questions? Some should go on SO and questions like this one are perfect here on CR. Questions about where to go for knowledge will be closed on SO, so books and hacking away is my answer to that. – Ted Lyngmo Apr 3 at 22:57

Declare for-loop-variables inside for instead of reusing them.

int v[501][501], i, j, m, n, o, p;
cin >> m >> n >> o >> p;
for (i = o; i >= 1; i--)
v[i][p] = o - i;
for(i = o;i <= m; i++)
v[i][p] = i - o;
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++){


use (except you should also change types and rename variables as suggested by @Ted Lyngmo ).

int v[501][501], m, n, o, p;
cin >> m >> n >> o >> p;
for (int i = o; i >= 1; i--)
v[i][p] = o - i;
for(int i = o;i <= m; i++)
v[i][p] = i - o;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++){


The reasons are:

• It's usual in C++
• Easier to find the declaration.
• No risk that the value is reused after the loop.
• Hello Hans! Thanks for the reply, noted regarding the variable, very good observation, I used to have problems in the past when I implemented a good algorithm but I didn't pay attention and used a a preexisting value from a for loop. Ted pointed out very interesting things that it's the 1st time I ever hear of, which is a shame because we learn C++ in school for 4 years... they never showed us anything like this. I find C++ very hard, and I currently taking a course where I use just the information given by the course creator. Must of the syntax from Ted's code was not presented in the course – nultype Apr 3 at 13:07
• it's a shame really, since I am almost finished with the c++ part of the course and soon I'll start OOP in Java. – nultype Apr 3 at 13:08
• I agree that it is a shame, and one possibility is that the C++ course is adapted from an old C-course with minimal changes (e.g., using the iostream-library). – Hans Olsson Apr 3 at 14:13
• how did you learn c++? are you an engineer currently working in C++? – nultype Apr 3 at 15:01