How to extract the indexes of the cells in the same diagonal of a 2D matrix C++

Question

As stated above, I am trying to get the elements of a 2D matrix using only C++ The matrix has MxN dimensions, and it may be so that N!=M, N >= M or M < N (basically the dimensions can be anything and are determined in execution time) I have tried to go about it using 2 nested for loops but so far the code just keeps getting more & more complex & does not produce consistent results.

Visual aid:

I am trying to get the 2nd for loop to iterate through the colored cells of the matrix starting from top left - i.e. in every loop the amount/position of the cells that the 2nd loop iterates through keeps changing & I am starting to wonder whether this can be done at all given that N & M are not known on compile time.

Thanks for your time in advance.

~EDIT1: Here is what the iteration of the elements would look like for a non square matrix (same thing applies if the rows where more than the columns)

~EDIT2: Here is the code so far: (testable!)

#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

void func(void);

// use these variables to specify the dimensions arbitrarily
// keep in mind I need this to work with relatively big matrices
int row = 5, col = 5;
string arr[][10]= {{"0",   "0",     "0",   "0",    "0",   "0",   "0",    "0",   "0",   "0"  },
       {"0",  "1,1",   "1,2", "1,3",  "1,4", "1,5", "1,6",  "1,7", "1,8", "1,9" },
       {"0",  "2,1",   "2,2", "2,3",  "2,4", "2,5", "2,6",  "2,7", "2,8", "2,9" },
       {"0",  "3,1",   "3,2", "3,3",  "3,4", "3,5", "3,6",  "3,7", "3,8", "3,9" },
       {"0",  "4,1",   "4,2", "4,3",  "4,4", "4,5", "4,6",  "4,7", "4,8", "4,9" },
       {"0",  "5,1",   "5,2", "5,3",  "5,4", "5,5", "5,6",  "5,7", "5,8", "5,9" },
       {"0",  "6,1",   "6,2", "6,3",  "6,4", "6,5", "6,6",  "6,7", "6,8", "6,9" },
       {"0",  "7,1",   "7,2", "7,3",  "7,4", "7,5", "7,6",  "7,7", "7,8", "7,9" },
       {"0",  "8,1",   "8,2", "8,3",  "8,4", "8,5", "8,6",  "8,7", "8,8", "8,9" },
       {"0",  "9,1",   "9,2", "9,3",  "9,4", "9,5", "9,6",  "9,7", "9,8", "9,9" }  };


bool f = false, f2 = false;

int main (void)
{
    func();
    return 0;
}

void func(void)
{

    if(row < col)
    {
        //remember that row > col
        f = true;
    }
    unsigned short m_i;       //mask for the counter of the outer for loop (i) - counts how many times the 
    unsigned short j_end = 1; //stores the max number of iterations the inner loop should do - increments accordingly
    unsigned short  k = 1;    //stores the starting index of the inner loop - starts incrementing once (j_end == col)
    cout << "row = " << row << ", col = " << col << endl;
    cout << "total \"i\" loops " << (row + col -1) << endl << endl;
    for (unsigned short i=1; i<=row + col -1; i++)   // row + col -1 is the total number of diagonals in any matrix
    {                                                // and also the total number of iterations we need
        if( i > row)      // here I implement the row > col scenario, the rest should be similar 
        {
             m_i = row;    // the mask should never go above the max row number 
        }else if(i == row)
        {
             m_i = row;
             if (f = true) f2 = true;    // using f2 remember that we've reached the max number for rows
        }else{
             m_i = i;     // (i < row) so just pass i
        }
    for(unsigned short j=k; j<=j_end; j++){      
        cout<< arr[m_i][j]<<" ";
        if(m_i > 1){               
            m_i--;
        }else{
            m_i = 1;
        }           
    }
    cout<<endl<< "*************" << endl;
    if(j_end == col )
    {                              
        k++;        // increment starting index of inner loop
    }else{
        j_end++;    // max number for inner loop not yet achieved so increment max number 
    }

    if(m_i == row)
    {
        k++;
    }
    } // end outer loop

}  // end func

You can use this code to test it for yourself the output should be something like this:

And you can change the row & col values to test for different dimensions. So far I believe this code works for square matrices, but not so much when row != col

~EDIT3: func() should take performance into consideration as I said before I expect the matrices to be quite large!

Answer 1

Code:

#include <vector>
#include <utility>
#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int> > result;
    for (int k = 0; k < m; k++) {
        int i = 0, j = k;
        while (i < n && j >= 0)
        {
            result.push_back({ i, j });
            i++;
            j--;
        }

    }

   for (int k = 1; k < n; k++) {
        int i = k, j = m - 1;
        while (i < n && j >= 0)
        {
            result.push_back({ i, j });
            i++;
            j--;
        }
    }

    return 0;
}

Explanations: If you look at the picture, you can see that diagonal is when you move i + 1 and j - 1. Until the first half, we start from the first row and try to go in direction specified. When we hit the end, we just go to the next column. Basically, every iteration we are just changing the starting point. The second part is a bit trickier, because we already traversed some of the lines, so we start from 1 (because we already traversed first row. Then applying the same direction as in the first half, we traverse the rest of the matrix.

Answer 2

for( int manhattan_distance = 0; manhattan_distance < M + N - 1; ++manhattan_distance )
{
    for( int i = 0; i <= manhattan_distance; ++i )
    {
         int j = manhattan_distance - i;
         if( j < N && i < M )
         {
               ...
         }       
    }
}

Answer 3

You can do it like this:

void foo(int rows,int cols){
    // first go vertically down
    for (int start_row = 0;start_row<rows;start_row++){
        int col = 0;
        int row = start_row;
        while (col < cols && row >= 0){
            std::cout << row << "," << col << " ";
            row--;
            col++;
        } 
        std::cout << std::endl;
    }
    // now horizantally
    for (int start_col = 0;start_col<cols;start_col++){
        int col = start_col;
        int row = rows-1;
        while (col < cols && row >= 0){
            std::cout << row << "," << col << " ";
            row--;
            col++;
        }
        std::cout << std::endl;
    }
}   

It might be possible to write it more compact, but it works.

Answer 4

OK I got an answer for this, all thought its not refined. It is working properly but it is not optimized.

EDIT: c#... did not see it was for c++, but the idea is the same

using System;
Random r = new Random();
int rows = r.Next(10,13); // or any range of rows
int cols = r.Next(10,20); // same applies
int[,] matrix = new int[rows,cols];

// mark upper diagonal
for(var i=0; i<= cols; i++)
    markByCol(i,0,cols-i);


// mark lower diagonal
for(var i=1; i<= rows; i++)
    markByCol(cols+1+i,i,cols-1);

// stringify matrix to view it properly
string line = string.Empty;
for(int i=0; i< rows; i++)
{
    line = string.Empty;
    for(int j=0; j< cols; j++)
    {
        line+= matrix[i,j]+" | ";
    }
    Console.WriteLine(line);
}

// the actual function
    int markByCol(int marker,int row,int col){
    if((row > -1  && row < rows) && (col > -1 && col < cols))
    {
            matrix[row,col] = marker;
        return markByCol(marker,row+1,col-1);
    }
    else
        return 0;   
}

Here is a jsFiddle. just hit play. This implementation marks each diagonal with a specific integer so you can scan and categorize each cell by its value, in terms of which diagonal crosses it. https://dotnetfiddle.net/Qy8J1O