CODEWITHSUNDEEP
c++algorithm
Savvas Savvidis
Savvas Savvidis

Reputation: 97

Is there a C++ function to calculate distance between two indexes?

There is a task in codingame, called 'Lumen', that I just solved. To summarize the task: in a square array, in random indexes the letter 'C' will be placed, representing a candle. The highest luminosity 'L' (int) will be placed at the index of letter 'C' and then, the luminosity for all neighboring indexes has to be calculated, until the value of L becomes 0. So in index arr[i][j] the luminosity will be set to L, for all combinations of arr[i-1][j] will be L-1 ad so on. Right now, in my code, I have very lengthy 'if' based calculation, for a maximum value of L = 3 (in the task it goes lower not higher). Here is some example code of the calculations: 

for(int i = 0; i < N; ++i){
    for (int j = 0; j < N; ++j){
        if (map[i][j] == 'C'){

    luminance[i][j] = L;
    if (i + 1 < N)  { luminance[i + 1][j] = L - 1; }
    if (i - 1 >=0)  { luminance[i - 1][j] = L - 1; }
    if (j + 1 < N)  { luminance[i][j + 1] = L - 1; }
    if (j - 1 >= 0) { luminance[i][j - 1] = L - 1; }
            ...
            ...
    if (i + 2 < N)  { luminance[i + 2][j] = L - 2; }
    if (i - 2 >= 0) { luminance[i - 2][j] = L - 2; } ...

Is there a better and less prone to bugs way to perform these calculations? I read somewhere, that essentially, this is an inverse Chebyshev distance calculation (max(|x1 -x2|,|y1-y2|). If it is so, is there a function to calculated it in C++? I searched a little about it and found documentation for python3 and java, but not for C++. Thank you for your time!

Upvotes: 1

Views: 902

Answers (1)

Holt
Holt

Reputation: 37606

Start by finding the index of the candle, and then simply iterate over all cells:

int col, row;

for (int i = 0; i < N; ++i){
    for (int j = 0; j < N; ++j){
        if (map[i][j] == 'C') {
            col = j;
            row = i;
        }
    }
}

Then simply iterate over all cells, compute the distance, and then the luminance:

#include <cstdlib>    // for std::abs
#include <algorithm>  // for std::max

for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        int distance = std::max(std::abs(i - row), std::abs(j - col));
        luminance[i][j] = std::max(L - distance, 0);
    }
}

Upvotes: 3

Related Questions