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

class Solution {
  public:

    bool isBound(int x, int y, int n, int m) {
        if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
            return false;
        }
        return true;
    }

    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };


    int recursion(int x, int y, vector<vector<int> >& matrix,
                  vector<vector<int>>& mark) {
        if (mark[x][y] != 0)
            return mark[x][y];
        int cmax = 0;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (isBound(tx, ty, matrix.size(), matrix[0].size())) {
                if (matrix[x][y] < matrix[tx][ty]) {
                    cmax = max(cmax, recursion(tx, ty, matrix, mark));
                    recursion(tx, ty, matrix, mark);
                }
            }
        }
        mark[x][y] = cmax + 1;
        return cmax + 1;
    }

    int solve(vector<vector<int> >& matrix) {
        // write code here
        int max = 0;
        vector<vector<int>> mark(matrix.size(), vector<int> (matrix[0].size(), 0));
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (recursion(i, j, matrix, mark) > max) {
                    max = recursion(i, j, matrix, mark);
                }
            }
        }
        return max;
    }
};