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). Problem is on this link https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Longest Increasing Path in a Matrix sample code

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]
]
#include<iostream>
#include<algorithm>
using namespace std;

#define N 20
int mat[N][N];

int dx[] = {-1, 0, 1,  0};
int dy[] = { 0, 1, 0, -1};

bool valid(int i, int j, int r, int c)
{
	if (i < 0 || j < 0 || i >= r || j >= c)
		return false;
	return true;
}
int solve(int i, int j, int r, int c)
{
	int ret = 1;
	for (int x = 0; x < 4; x++)
	{
		int ii = dx[x] + i;
		int jj = dy[x] + j;
		if (valid(ii, jj, r, c))
		{
			if (mat[i][j] < mat[ii][jj])
			{
				ret = max(ret, solve(ii, jj, r, c) + 1);
			}
		}
	}
	return ret;
}
int main()
{
	freopen("input.txt", "r", stdin);
	int t = 0;
	cin >> t;
	for (int test = 0; test < t; test++)
	{
		int ans = 0;
		int row = 0;
		int col = 0;
		cin >> row >> col;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				cin >> mat[i][j];
			}

		}

		// solution
		int max = 0;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				int a = solve(i, j, row, col);
				// update max
				if (max < a)
					max = a;
			}

		}
		ans = max;
		cout << ans << endl;
	}
	return 0;
}


Related Contents to follow