-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path0329-LongestIncreasingPathInAMatrix.cs
41 lines (36 loc) · 1.39 KB
/
0329-LongestIncreasingPathInAMatrix.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//-----------------------------------------------------------------------------
// Runtime: 132ms
// Memory Usage:
// Link:
//-----------------------------------------------------------------------------
using System;
namespace LeetCode
{
public class _0329_LongestIncreasingPathInAMatrix
{
private readonly static int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
public int LongestIncreasingPath(int[][] matrix)
{
if (matrix.Length == 0) return 0;
int M = matrix.Length, N = matrix[0].Length;
var cache = new int[M, N];
var maxValue = 0;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
maxValue = Math.Max(maxValue, DFS(cache, matrix, M, N, i, j));
return maxValue + 1;
}
private int DFS(int[,] cache, int[][] matrix, int M, int N, int i, int j)
{
if (cache[i, j] != 0) return cache[i, j];
foreach (var dir in dirs)
{
int x = i + dir[0], y = j + dir[1];
if (0 <= x && x < M && 0 <= y && y < N)
if (matrix[x][y] > matrix[i][j])
cache[i, j] = Math.Max(cache[i, j], DFS(cache, matrix, M, N, x, y) + 1);
}
return cache[i, j];
}
}
}