Click here to Skip to main content
14,732,816 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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:

#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 8:14am
Comments
Patrice T 28-Apr-18 19:47pm
   
How do you define "longest increasing matrix" ?

1 solution

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?
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)




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