C# Solution


  • 0
    T
        public class Node
        {
            public int Row { get; set; }
            public int Col { get; set; }
            public Node(int r, int c)
            {
                Row = r;
                Col = c;
            }
            public List<Node> Children { get; set; } = new List<Node>();
        }
        public class GolfTree : Node, IComparable<GolfTree>
        {
            public int Height { get; set; }
            public GolfTree(int r, int c, int h)
                : base(r, c)
            {
                Height = h;
            }
    
            public int CompareTo(GolfTree other)
            {
                return Height.CompareTo(other.Height);
            }
        }
        public class Solution
        {
            bool[,] IsVisited;
            int[,] ShortestDistances;
    
            Node[,] Graph { get; set; }
            List<GolfTree> Trees { get; set; } = new List<GolfTree>();
            void BuildGraph (IList<IList<int>> forest )
            {
                int nRows = forest.Count;
                int nCols = forest[0].Count;
    
                Graph = new Node[nRows, nCols];
    
                for (int i=0; i<nRows; ++i)
                {
                    for (int j=0; j<nCols; ++j)
                    {
                        if (forest[i][j] == 0)
                        {
                            Graph[i, j] = null;
                            continue;
                        }
    
                        var node = new Node(i, j);
                        Graph[i, j] = node;
    
                        if (i > 0) // up possible
                        {
                            var up = Graph[i - 1, j];
                            if (up != null )
                            {
                                node.Children.Add(up);
                                up.Children.Add(node);
                            } 
                        }
                        if ( j > 0 ) // left possible
                        {
                            var left = Graph[i, j -1 ];
                            if (left != null)
                            {
                                node.Children.Add(left);
                                left.Children.Add(node);
                            }
                        }
    
                        if (forest[i][j] > 1)
                        {
                            Trees.Add(new GolfTree(i,j,forest[i][j]));
                        }
                    }
                }
            }
    
            int computeDistance (Node start, Node end, IList<IList<int>> forest)
            {
                if (forest[start.Row][start.Col] == 0)
                    return -1;
    
                int height = forest.Count;
                int width = forest[0].Count;
    
                IsVisited = new bool[height, width];
                ShortestDistances = new int[height, width];
    
                for (int i=0; i<height; i++)
                {
                    for (int j=0; j<width; ++j)
                    {
                        ShortestDistances[i, j] = int.MaxValue;
                    }
                }
    
                var currentPositions = new List<Node>();
                currentPositions.Add(start);
                ShortestDistances[start.Row, start.Col] = 0;
    
                while (currentPositions.Count > 0)
                {
                    var nextPositions = new List<Node>();
    
                    foreach (var curPos in currentPositions)
                    {
                        if (curPos.Row == end.Row && curPos.Col == end.Col)
                            return ShortestDistances[curPos.Row, curPos.Col];
    
                        if (IsVisited[curPos.Row, curPos.Col])
                            continue;
    
                        var new_distance = ShortestDistances[curPos.Row, curPos.Col] + 1;
    
                        foreach (var nextPos in curPos.Children )
                        {                        
                            if (!IsVisited[nextPos.Row, nextPos.Col] &&
                                new_distance <= ShortestDistances[nextPos.Row, nextPos.Col])                         
                            {
                                ShortestDistances[nextPos.Row, nextPos.Col] = new_distance;
                                nextPositions.Add(nextPos);
                            }
                        }
    
                        IsVisited[curPos.Row, curPos.Col] = true;
                    }
    
                    currentPositions = nextPositions;
                }
    
                return -1;
            }
            public int CutOffTree(IList<IList<int>> forest)
            {
                if (forest[0][0] == 0)
                    return -1;
                
                int nRow = forest.Count;
                int nCol = forest[0].Count;
    
                BuildGraph(forest);
    
                Trees.Sort();
    
                var start = Graph[0,0];
                int totalWalk = 0;
    
                foreach (var tree in Trees)
                {
                    var end = Graph[tree.Row, tree.Col];
                    var walk = computeDistance(start, end, forest);
                    if (walk == -1)
                        return -1;
                    forest[end.Row][end.Col] = 1;
                    totalWalk += walk;
                    start = end;
                }
    
                return totalWalk;
            }
        }
    

Log in to reply
 

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