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

Question

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?

Answer 1

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

Answer 2

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

So instead of:

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.