# C# solution: memorization and DFS

• ``````public class Solution
{
private Dictionary<Tuple<int,int>, int> positionAndLongestIncreasingCount = new Dictionary<Tuple<int,int>, int>();
private Tuple<int,int>[] directions = new Tuple<int,int>[]{ Tuple.Create(0,1), Tuple.Create(0,-1), Tuple.Create(-1, 0), Tuple.Create(1,0)};
public int LongestIncreasingPath(int[,] matrix)
{
var row = matrix.GetLength(0);
var col = matrix.GetLength(1);

var global = 0;

for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
var local = DFS(matrix, i, j, long.MinValue);

global = Math.Max(global, local);
}
}

return global;
}

private int DFS(int[,] matrix, int x, int y, long preValue)
{
var row = matrix.GetLength(0);
var col = matrix.GetLength(1);

if (x < 0 || x >= row || y < 0 || y >= col) return 0;
if (matrix[x, y] <= preValue) return 0;

var curPosition = Tuple.Create(x, y);

if (positionAndLongestIncreasingCount.ContainsKey(curPosition))
return positionAndLongestIncreasingCount[curPosition];

var global = 0;
foreach(var direction in directions)
{
var nextX = x + direction.Item1;
var nextY = y + direction.Item2;

var local = DFS(matrix, nextX, nextY, matrix[x,y]);

global = Math.Max(global, local);
}

global += 1;

positionAndLongestIncreasingCount[curPosition] = global;

return global;
}
}
``````

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