Printing the longest increasing path in a matrix

See more:

C++

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:

#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;

}