C# using queue for BFS and stack for distances.


  • 0
    J

    I created a class Node to represent an element and all the necessary properties associated with the element, like the distances of that element from the buildings, the number of buildings it has access to. This is a simple BFS solution. I used a stack to store the distances, so that everytime I did stack.Peek(), I would get the distance associated with a particular building.

    public class Solution {
        
        int gridlength = 0;
        int gridbreadth = 0;
        Queue<Node> queue = new Queue<Node>();
        Dictionary<int, Node> dic = new Dictionary<int, Node>(); 
        HashSet<Node> visited = new HashSet<Node>();
        int totalbuildingcount = 0;
        // dictionary to store index of element as key, and Node object
        // for that element as value
        
        public int ShortestDistance(int[,] grid) 
        {
            gridlength = grid.GetLength(0);
            gridbreadth = grid.GetLength(1);
            if (gridlength == 0 || gridbreadth == 0) return 0;
            var list = new List<Node>();
            for (int rowindex = 0; rowindex < gridlength; rowindex++)
            {
                for (int colindex = 0; colindex < gridbreadth; colindex++)
                {
                    var newnode = new Node(rowindex, colindex);
                    newnode.value = grid[rowindex, colindex];
                    newnode.row = rowindex;
                    newnode.col = colindex;
                    newnode.index = (rowindex*gridbreadth) + colindex;
                    dic.Add(newnode.index, newnode);
                    if (newnode.value == 1) 
                    {
                        list.Add(newnode);
                        newnode.distance.Push(0);
                    }
                }
            }
            totalbuildingcount = list.Count;
            // Here, at the end of the for loop, we have a dictionary of all the elements represented as nodes. 
            // We also have all the building nodes in a queue. For each building node, we will get the distance of all the 0
            // elements from that building.
            
            foreach (var n in list)
            {
                queue.Enqueue(n);
                while(queue.Count != 0)
                {
                    var node = queue.Dequeue();
                    var row1 = node.row+1; var col1 = node.col;
                    var row2 = node.row-1; var col2 = node.col;
                    var row3 = node.row; var col3 = node.col+1;
                    var row4 = node.row; var col4 = node.col-1;
                    
                    Neighbor (row1, col1, node);
                    Neighbor (row2, col2, node);
                    Neighbor (row3, col3, node);
                    Neighbor (row4, col4, node);
                }
                visited.Clear();
            }
            var result = int.MaxValue;
            foreach (var element in dic.Keys)
            {
                var node = dic[element];
                if (node.value == 0 && node.distance.Count > 0 && node.buildingcount == totalbuildingcount)
                {
                    var distancesum = 0;
                    while(node.distance.Count > 0)
                    {
                        distancesum += node.distance.Pop();
                    }
                    result = Math.Min(result, distancesum);
                }
            }
            return result == int.MaxValue ? -1 : result;
        }
        
        private void Neighbor(int row, int col, Node n)
        {
            if (IsValid(row, col))
            {
                var thisnode = dic[((row*gridbreadth)+col)];
                if (n.value != 2 && thisnode.value != 1 && thisnode.value != 2 && !visited.Contains(thisnode))
                {
                    thisnode.distance.Push(n.distance.Peek()+1);
                    thisnode.buildingcount++;
                    visited.Add(thisnode);
                    queue.Enqueue(thisnode);
                }
            }
        }
        
        private bool IsValid(int row, int col)
        {
            return (row >= 0 && row < gridlength && col >= 0 && col < gridbreadth);
        }
        
    }
    
    public class Node
        {
            public int value { get; set;} // the value of this element in the matrix
            public int row { get; set;} // the row number of this element
            public int col { get; set;} // the column number of this element
            public int buildingcount = 0;
            public Stack<int> distance = new Stack<int>(); // The distance of this element from all the buildings (summation)
            public int index { get; set;} // The index is an integer that represents this element. Calculated from row and col
            public Node(int r, int c)
            {
                row = r;
                col = c;
            }
        }
    

Log in to reply
 

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