C# solution: memorization and DFS


  • 0
    B
    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;
        }
    }
    

Log in to reply
 

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