题解 | #矩阵最长递增路径#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};

    int solve(vector<vector<int> >& matrix) {//方法一，直接dfs
        // write code here
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        int maxPath = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                maxPath = max(maxPath, dfs1(matrix, i, j));
            }
        }

        return maxPath;
    }

    int dfs1(vector<vector<int>>& matrix, int x, int y) {
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        int maxPath = 1;
        for (int i = 0; i < 4; ++i) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m)
                continue;
            if (matrix[next_x][next_y] <= matrix[x][y])
                continue;

            maxPath = max(maxPath, 1 + dfs1(matrix, next_x, next_y));
        }

        return maxPath;
    }

    int solve2(vector<vector<int> >& matrix) {//方法二，动态规划+dfs
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        vector<vector<int>> dp(n, vector<int>(m));

        int maxPath = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                maxPath = max(maxPath, dfs2(matrix, dp, i, j));
            }
        }

        return maxPath;
    }

    int dfs2(vector<vector<int> >& matrix, vector<vector<int>>& dp, int x, int y) {
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        if (dp[x][y])
            return dp[x][y];

        dp[x][y] = 1;
        for (int i = 0; i < 4; ++i) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m)
                continue;
            if (matrix[next_x][next_y] <= matrix[x][y])
                continue;

            dp[x][y] = max(dp[x][y], 1 + dfs2(matrix, dp, next_x, next_y));
        }

        return dp[x][y];
    }


    int solve3(vector<vector<int>>& matrix) { //方法三，广度优先搜索
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        int maxPath = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j)
                maxPath = max(maxPath, bfsMaxLength(matrix, i, j));
        }
        return maxPath;
    }

    int bfsMaxLength(vector<vector<int>>& matrix, int x, int y) {
        int n = matrix.size();
        if (n == 0)return 0;
        int m = matrix[0].size();

        int temp = 0;

        queue<pair<int, int>> q;
        q.push({ x, y });
        while (!q.empty()) {
            temp++;
            int num = q.size();
            for (int k = 0; k < num; ++k) {
                pair<int, int> pos = q.front();
                q.pop();
                int x = pos.first, y = pos.second;
                for (int l = 0; l < 4; ++l) {
                    int next_x = x + dx[l];
                    int next_y = y + dy[l];
                    if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m &&
                            matrix[next_x][next_y] > matrix[x][y])
                        q.push({ next_x, next_y });
                }
            }
        }
        return temp;
    }

};