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