329 Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4. The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4. The longest increasing path is [3, 4, 5, 6].

Solution

class Solution {
public:
    void help(vector<vector<int>>& matrix, unordered_map<int, vector<int>>& graph, vector<int>& inorder, int i, int j, int i1, int j1) {
        int m = matrix.size(), n = matrix[0].size();
        if ( i1 <= -1 or i1 >= m or j1 <= -1 or j1 >= n ) return;
        if ( matrix[i1][j1] > matrix[i][j] ) {
            graph[i*n+j].push_back(i1*n+j1);
            inorder[i1*n+j1] += 1;
        }
        return;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if ( m == 0 ) return 0;
        int n = matrix[0].size();
        if ( n == 0 ) return 0;
        unordered_map<int, vector<int>> graph;
        vector<int> inorder(m*n, 0);
        for ( int i = 0; i <= m-1; i++ ) {
            for ( int j = 0; j <= n-1; j++ ) {
                help(matrix, graph, inorder, i, j, i-1, j);
                help(matrix, graph, inorder, i, j, i+1, j);
                help(matrix, graph, inorder, i, j, i, j-1);
                help(matrix, graph, inorder, i, j, i, j+1);
            }
        }
        int length = 0, left = m*n;
        while ( true ) {
            int curr = left;
            vector<int> tmp = inorder;
            for ( int i = 0; i <= m-1; i++ ) {
                for ( int j = 0; j <= n-1; j++ ) {
                    if ( inorder[i*n+j] != 0 ) continue;
                    for ( int k : graph[i*n+j] ) tmp[k] -= 1;
                    tmp[i*n+j] = -1;
                    left -= 1;
                }
            }
            if ( left == curr ) break;
            length += 1;
            inorder.swap(tmp);
        }
        return max(1, length);
    }
};

Notes
The key is to convert this problem to a graph data structure.