15,900,907 members
See more:
The problem came from here.

I am trying to simply print out the entries of the longest increasing matrix. I thought I had it figure out when I tried the following matrix:

2 2 1
1 2 1
2 2 1

I got an output of:

1
2

Then when I increased n , m = 4. I got this matrix:

2 2 1 1
2 1 2 2
1 2 2 3
1 2 1 3
And this output for the paths entries:

1
1
2

When it should be just:

1
2
3

Code is at the bottom:

What I have tried:

C++
```#include <algorithm>
#include <cmath>
#include <list>
#include <vector>
#include <stdio.h>
#include <random>
#include <utility>
#include <iostream>

void printPath(std::vector<int> &numPaths) {
std::sort(numPaths.begin(), numPaths.end());
for(int i = 0; i < numPaths.size(); i++) {
std::cout << numPaths[i] << std::endl;
}

}

int DFS(int i, int j, const std::vector<std::vector<int> > &matrix, std::vector<std::vector<int> > &length) {
std::vector<std::pair<int,int> > dics{{-1,0},{1,0},{0,-1},{0,1}}; // used to check the directions left, right, up, down
std::vector<int> path;
if(length[i][j] == -1) {
int len = 0;
for(auto p: dics) {
int x = i + p.first, y = j + p.second;
if(x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) continue; // Check to make sure index is not out of boundary
if(matrix[x][y] > matrix[i][j]) { // compare number
len = std::max(len, DFS(x,y,matrix,length));
}
}
length[i][j] = len + 1;
}
return length[i][j];
}

int longestPath(std::vector<std::vector<int> > matrix) {
int n = matrix[0].size();
if (n == 0) {
return 0;
}
int m = matrix.size();
if (m == 0) {
return 0;
}
std::vector<std::vector<int> > length(m, std::vector<int>(n,-1));
std::vector<int> numPaths;

int len = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int newLen = DFS(i,j,matrix,length);
if(newLen > len) {
numPaths.push_back(matrix[i][j]);
}
len = std::max(len, DFS(i, j, matrix, length));
}
}
printPath(numPaths);
return len;
}

int main() {
// Specify the number of rows and columns of the matrix
int n = 4;
int m = 4;

// Declare random number generator
std::mt19937 gen(10);
std::uniform_int_distribution<> dis(1, 3);

// Fill matrix
std::vector<std::vector<int> > matrix;
for(int i = 0; i < m; i++) {
std::vector<int> row;
for(int j = 0; j < n; j++) {
row.push_back(0);
}
matrix.push_back(row);
}

// Apply random number generator to create matrix
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
matrix[i][j] = dis(gen);
}
}

// Print matrix to see contents
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
std::cout << matrix[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;

int result = longestPath(matrix);
std::cout << "The longest path is " << result << std::endl;

}```
Posted
Updated 29-Apr-18 7:14am
Patrice T 28-Apr-18 19:47pm
How do you define "longest increasing matrix" ?

## Solution 1

A classical debugging problem, so learn to use the debugger. In the tutorial Debugging your program (watching variables and the call stack) you may learn some useful details.

Why didnt you write that?
C++
```len = std::max(len,newLen);
```

Tip: write logging output, at best when negative returning from functions.

Why are sorting in printPath? This may print some other data than the original input.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 OriginalGriff 80 Pete O'Hanlon 65 Member 1408653 10 Rajesh Pandya 5 Eddy Sels 2021 -6
 Pete O'Hanlon 1,490 OriginalGriff 1,132 Richard MacCutchan 325 Richard Deeming 300 Dave Kreskowiak 280

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900