c# Accepted Solution! DFS & DP


  • 0
    R

    public class Solution {
    private int m;
    private int n;
    private int[,] matrix;
    private int[,] dp;
    public int LongestIncreasingPath(int[,] matrix)
    {
    this.matrix = matrix;
    m = matrix.GetLength(0);
    n = matrix.GetLength(1);
    if ((long)m * n == 0)
    return 0;
    dp = new int[m, n];
    int result = 1;
    bool[,] visited = new bool[m, n];
    for (int i = 0; i < m; i++)
    {
    for (int j = 0; j < n; j++)
    {
    result = Math.Max(result, LongestIncreasingPathHelper(visited, i, j));
    }
    }

            return result;
        }
        private int LongestIncreasingPathHelper(bool[,] visited, int x, int y)
        {
            int curr;
            int result = 1;
            visited[x, y] = true;
            // to right(have value on right && right value isn't visited && right value > curr)
            if (y < (n - 1) && !visited[x, y + 1] && matrix[x, y + 1] > matrix[x, y])
            {
                if(dp[x, y+1] >0)
                    curr = dp[x, y+1];
                else
                {
                    curr = LongestIncreasingPathHelper(visited, x, y + 1);
                }
                
                result = Math.Max(result, curr+1);
            }
    
            // to left
            if (y > 0 && !visited[x, y - 1] && matrix[x, y - 1] > matrix[x, y])
            {
                if (dp[x, y - 1] > 0)
                    curr = dp[x, y - 1];
                else
                {
                    curr = LongestIncreasingPathHelper(visited, x, y - 1);
                }
    
                result = Math.Max(result, curr+1);
            }
    
            // to down
            if (x < (m-1) && !visited[x+1, y] && matrix[x+1, y] > matrix[x, y])
            {
                if (dp[x+1, y] > 0)
                    curr = dp[x+1, y];
                else
                {
                    curr = LongestIncreasingPathHelper(visited, x+1, y);
                }
    
                result = Math.Max(result, curr+1);
            }
    
            // to up
            if (x > 0 && !visited[x - 1, y] && matrix[x - 1, y] > matrix[x, y])
            {
                if (dp[x - 1, y] > 0)
                    curr = dp[x - 1, y];
                else
                {
                    curr = LongestIncreasingPathHelper(visited, x - 1, y);
                }
    
                result = Math.Max(result, curr+1);
            }
    
            visited[x, y] = false;
            dp[x,y] = result;
            return result;
        }
    

    }


Log in to reply
 

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