C++ 329. Longest Increasing Path in a Matrix CHATGPT UNLIMITED

cpp
#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) {
            return 0;
        }

        int rows = matrix.size();
        int cols = matrix[0].size();
        int maxPath = 0;

        std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                maxPath = std::max(maxPath, dfs(matrix, dp, i, j, rows, cols));
            }
        }

        return maxPath;
    }

private:
    int dfs(std::vector<std::vector<int>>& matrix, std::vector<std::vector<int>>& dp, int i, int j, int rows, int cols) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int maxPath = 1;

        for (auto dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];

            if (x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > matrix[i][j]) {
                maxPath = std::max(maxPath, 1 + dfs(matrix, dp, x, y, rows, cols));
            }
        }

        dp[i][j] = maxPath;
        return maxPath;
    }
};


In this implementation, the `longestIncreasingPath` function initializes a dynamic programming table `dp` to store the length of the longest increasing path starting from each cell in the matrix. It then iterates through each cell in the matrix and uses a depth-first search (dfs) function to calculate the longest increasing path starting from that cell.

The `dfs` function recursively explores all possible directions from a cell and updates the `dp` table with the length of the longest increasing path starting from that cell. Finally, the `longestIncreasingPath` function returns the maximum path length found in the matrix.