C++ Solution without dfs


  • 0

    The basic idea is that for each cell, we always try to "push" it up if there exists a neighbor which has smaller value but in a higher or equal height. The overall running time should be O((MN)^2).

       int longestIncreasingPath(vector<vector<int>>& matrix) {
        		const size_t RN = matrix.size();
        		if (RN == 0)
        			return 0;
        		const size_t CN = matrix[0].size();
        		vector<int> m(RN*CN);
        		for (;;)
        		{
        			bool update = false;
        			vector<int> m2(m.begin(), m.end());
        			for (size_t r = 0; r < RN; r++)
        				for (size_t c = 0; c < CN; c++)
        				{
        					if (r > 0 && matrix[r - 1][c] < matrix[r][c] && m[(r - 1)*CN + c] >= m[r*CN + c])
        					{
        						update = true;
        						m2[r*CN + c] = m[(r - 1)*CN + c] + 1;
        					}
        					if (r +1<RN && matrix[r + 1][c] < matrix[r][c] && m[(r + 1)*CN + c] >= m[r*CN + c])
        					{
        						update = true;
        						m2[r*CN + c] = m[(r + 1)*CN + c] + 1;
        					}
        					if (c > 0 && matrix[r ][c-1] < matrix[r][c] && m[r*CN + c-1] >= m[r*CN + c])
        					{
        						update = true;
        						m2[r*CN + c] = m[r*CN + c - 1] + 1;
        					}
        					if (c+1<CN && matrix[r][c + 1] < matrix[r][c] && m[r*CN + c + 1] >= m[r*CN + c])
        					{
        						update = true;
        						m2[r*CN + c] = m[r*CN + c + 1] + 1;
        					}
        				}
        			m = m2;
        			if (!update)
        				break;
        		}
        		int ret = 0;
        		for (auto v : m)
        			ret = max(ret, v);
        		return ret + 1;
        	}

Log in to reply
 

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