52 ms CPP DFS with hashMap solution


  • 0
    F
    class Solution {
        int DFS(vector<int> & mat, vector<int> & hasMap, int pos, const int COLS) {
            if (hasMap[pos]) return hasMap[pos];
            int v = mat[pos];
            mat[pos] = INT_MIN;
            int maxlen = 1;
    #define try_pos(p) { \
            int npos = (p); \
            if (mat[npos] > v) { \
                int l = DFS(mat, hasMap, npos, COLS)+1; \
                if (l > maxlen) maxlen = l; \
            } }
            try_pos(pos+1)
            try_pos(pos-1) 
            try_pos(pos-COLS-1) 
            try_pos(pos+COLS+1) 
            mat[pos] = v;
            hasMap[pos] = maxlen;
            return maxlen;
    
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if (matrix.empty())return 0;
            int COLS = matrix.front().size();
            vector<int> mat(COLS + 1, INT_MIN);
            for (auto & row : matrix) {
                mat.push_back(INT_MIN);
                mat.insert(mat.end(), row.begin(), row.end());
            }
            mat.insert(mat.end(), COLS + 1, INT_MIN);
            vector<int> hasMap(mat.size(), 0);
            int maxL = 0;
            for (int i = COLS+2; i < mat.size() - COLS - 1; i++) {
                if (mat[i] != INT_MIN && hasMap[i] == 0) {
                    int l = DFS(mat, hasMap, i, COLS);
                    if (l > maxL) maxL = l;
                }
            }
            return maxL;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.