Printing out the longest increasing path in a matrix

Question

I made a similar post on here but didn't get any feedback. 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

Here is my code:

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

    //std::vector<std::vector<int> > mat = {{1,2,3}};

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

}

I would really appreciate if someone can tell me where I am going wrong.

Answer 1

#include <algorithm>
#include <cmath>
#include <vector>
#include <stdio.h>
#include <random>
#include <utility>
#include <iostream>

#define MATRIX_SIZE 1000

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];
}

void printMatrix(std::vector<std::vector<int>> &matrix) {
    for (int i =0; i < matrix.size(); i++) {
        for (int j =0; j < matrix[0].size(); j++) {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

std::vector<int> generatePath(int i, int j, const std::vector<std::vector<int>> &matrix, const std::vector<std::vector<int>> &length) {

    int max_length = length[i][j];
    std::vector<int> path(max_length, 0);

    for (int current_length = max_length; current_length >= 1; current_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

        int index = max_length - current_length;
        for (auto p: dics) {

            path[index] = matrix[i][j];
            int x = i + p.first, y = j + p.second;
            if(x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) continue;
            if (current_length - length[x][y] == 1) {
                i = x;
                j = y;
                break;
            }
        }
    }

    printPath(path);

    return path;
}



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;
    int maxRow = 0;
    int maxCol = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int currentLength = DFS(i, j, matrix, length);
            if (currentLength > len) {
                len = currentLength;
                maxRow = i;
                maxCol = j;
            }
        }
    }
    generatePath(maxRow, maxCol, matrix,length);
    return len;
}

int main(int argc, char *argv[]) {
    std::mt19937 gen(10);
    std::uniform_int_distribution<> dis(1, 1000000);

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

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

    // Print matrix
    //printMatrix(matrix);



    timespec start, end;
    clock_gettime(CLOCK_REALTIME, &start);
    printf("the longest path is %d\n", longestPath(matrix));
    clock_gettime(CLOCK_REALTIME, &end);
    printf("found in %ld micros\n", (end.tv_sec * 1000000 + end.tv_nsec / 1000) - (start.tv_sec * 1000000 + start.tv_nsec / 1000));





    return 0;
}

Answer 2

# Print the Longest Increasing Path in a Matrix #
class Solution:
  
  # Possible directions allowed from the given question.
  DIRECTIONS = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  def longestIncreasingPath(self, matrix):
    # From the given question:
      # ----- m = rows ----- i
      # ----- n = cols ----- j
    m = len(matrix)
    if m == 0:
      return 0
    n = len(matrix[0])
    if n == 0:
      return 0
    
    cache = [[0] * n for _ in range(m)]
    longestPath = 0
    maximum = 1
    for i in range(m):
      for j in range(n):
        longestPath = self.depthFirstSearch(matrix, i, j, m, n, cache)
        maximum = max(maximum, longestPath)
    return (cache, maximum)

  def depthFirstSearch(self, matrix, i, j, m, n, cache):
    if cache[i][j] != 0:
      return cache[i][j]
    maxPath = 1
    for direction in self.DIRECTIONS:
      x = direction[0] + i
      y = direction[1] + j
      if x < 0 or y < 0 or x >= m or y >= n or matrix[x][y] <= matrix[i][j]:
        continue
      length = 1 + self.depthFirstSearch(matrix, x, y, m, n, cache)
      maxPath = max(maxPath, length)
    
    cache[i][j] = maxPath    # Save the value at i, j for future usage.
    return maxPath

  def printPath(self, matrix):
    # Check if longestPath is 0.
    if not self.longestIncreasingPath(matrix):
      return None
  
    length = self.longestIncreasingPath(matrix)[1]
    cache = self.longestIncreasingPath(matrix)[0]
    # From the given question:
    # ----- m = rows ----- i
    # ----- n = cols ----- j
    m = len(cache)
    n = len(cache[0])
    location = []
    # Traverse the cache to obtain the location of the starting point of the longest increasing path in the matrix.
    # Time complexity, T(n) = O(n*m) ----- if not a square matrix.
    for i in range(m):
      for j in range(n):
        if cache[i][j] == length:
          location.extend([i, j])
    
    i, j = location[0], location[1]
    result = [matrix[i][j]]       # The result container is initialised with the element of the matrix at the obtained position

    # Time complexity, T(n) = O(4n) ----- where n = length of longest increasing path in the given matrix and the 4 being the length of the DIRECTIONS matrix.
    for _ in range(length):                           
      for direction in self.DIRECTIONS:
        x = direction[0] + i
        y = direction[1] + j
        if x < 0 or y < 0 or x >= m or y >= n or cache[i][j] - 1 != cache[x][y]:
          continue
        result.append(matrix[x][y])
        i = x
        j = y

    return result