Description

Submission

class Solution {
    typedef pair<int, int> PII;
    vector<PII> dirs;
    int m, n;
    vector<vector<int>> matrix;
    int maxVal[201][201];

    vector<PII> Next(int i, int j) {
        vector<PII> rets;
        for(auto [dm, dn]: dirs) {
            int x = i + dm, y = j + dn;
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                rets.push_back({x, y});
            }
        }
        return rets;
    }

    int dfs(int x, int y, int cur) {
        if(cur <= maxVal[x][y]) return 0;
        maxVal[x][y] = cur;
        auto pairs = Next(x, y);
        if(pairs.empty()) return 1;

        int ret = 0;
        for(auto [a, b]: pairs) {
            ret = max(dfs(a, b, cur + 1), ret);
        }
        
        return ret + 1;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();

        this->matrix = matrix;
        
        dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        vector<vector<int>> haveIn(m, vector<int>(n, 0));

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                for(auto [x, y]: Next(i, j)) {
                    haveIn[x][y] = 1;
                }
            }
        }

        queue<PII> q; // {pair, maxVal}
        int ret = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(!haveIn[i][j]) {
                    ret = max(dfs(i, j, 1), ret);
                }
            }
        }

        return ret;
    }
};