Longest Increasing Path in a Mat

题目来源
给一个矩阵，求里面的最长递增路径长度。
看到这道题就想到微软面试的那道题目。
先把所有元素排序，然后找到各个元素，通过周边比它大的元素的最长递增路径长度来设定它的最长递增路径长度。最后再遍历一遍得到答案。
代码如下：

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0)
            return 0;
        int cols = matrix[0].size();
        vector<int> all;
        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        unordered_map<int, vector<pair<int, int>>> maps;
        for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++)
                all.push_back(matrix[i][j]);
        sort(all.begin(), all.end());
        vector<vector<int>> dp(rows, vector<int>(cols, 1));
        for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++)
                maps[matrix[i][j]].push_back(make_pair(i, j));
        for (int i=all.size()-1; i>=0; i--) {
            for (int j=0; j<maps[all[i]].size(); j++) {
                int x = maps[all[i]][j].first, y = maps[all[i]][j].second;
                for (int k=0; k<4; k++) {
                    int new_x = x + dirs[k][0], new_y = y + dirs[k][1];
                    if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && matrix[new_x][new_y] > matrix[x][y])
                        dp[x][y] = max(dp[x][y], dp[new_x][new_y] + 1);
                }
            }
            while (i-1>=0 && all[i-1] == all[i])
                i--;
        }
        int longest = 0;
        for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++)
                longest = max(longest, dp[i][j]);
        return longest;
    }
};

还有另一种方法就是每个cell做dfs遍历，然后对于已经遍历过的，存储下它的最长递增序列。代码如下：

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0)
            return 0;
        int cols = matrix[0].size();
        int longest = 0;
        vector<vector<int>> cache(rows, vector<int>(cols, 0));
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++) {
                longest = max(longest, dfs(matrix, i, j, rows, cols, dirs, cache));
            }
        return longest;
    }
        
    int dfs(vector<vector<int>>& matrix, int x, int y, int rows, int cols, const vector<vector<int>>& dirs, vector<vector<int>>& cache)
    {
        if (cache[x][y] != 0)
            return cache[x][y];
        int len = 1;
        for (auto dir : dirs) {
            int new_x = x + dir[0], new_y = y + dir[1];
            if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && matrix[new_x][new_y] > matrix[x][y])
                len = max(len, dfs(matrix, new_x, new_y, rows, cols, dirs, cache) + 1);
        }
        cache[x][y] = len;
        return len;
    }
};