# C++ Solution without dfs

• 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;
}``````

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