Leetcode 317 - shortest distance to all buildings - a warm up practice

Leetcode317ShortestDistanceToAllBuildingsMay112006.cpp

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode317_ShortestDistanceFromAllBuildings
{
    /*
    * Leetcode 317:
    * You want to build a house on an empty land which reaches all buildings in the shortest amount 
    * of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, 
    * where:
       Each 0 marks an empty land which you can pass by freely.
       Each 1 marks a building which you cannot pass through.
       Each 2 marks an obstacle which you cannot pass through.
       For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):
   1 - 0 - 2 - 0 - 1
   |   |   |   |   |
   0 - 0 - 0 - 0 - 0
   |   |   |   |   |
   0 - 0 - 1 - 0 - 0
    * 
    * The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is 
    * minimal. So return 7.
    * 
    * code reference:
    * http://buttercola.blogspot.ca/2016/01/leetcode-shortest-distance-from-all.html
    * 
    * Analysis from the above blog:
    * Note:
       There will be at least one building. If it is not possible to build such house according to       
       the above rules, return -1.
       Understand the problem:
       A BFS problem. Search from each building and calculate the distance to the building. 
    *  One thing to note is an empty land must be reachable by all buildings. To achieve this, 
    *  maintain an array of counters. Each time we reach a empty land from a building, increase the 
    *  counter. Finally, a reachable point must have the counter equaling to the number of buildings. 
    *    
    *  
    */
    class Node
    {
        public int x;
        public int y;
        public int distance;

        public Node(int a, int b, int dis = 0)
        {
            x = a;
            y = b;
            distance = dis;
        }
    }

    class Solution
    {
        const int EMTPYLAND = 0;
        const int BUILDING = 1;
        const int OBSTACLE = 2;

        private int getTotalBuildingsCount(int[,] grid, int rows, int cols)
        {             
            int count = 0;
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                {
                    if (grid[i, j] == BUILDING)
                        count++;
                }
            return count;
        }

        private IList<Node> getBuildings(int[,] grid, int rows, int cols)
        {
            IList<Node> list = new List<Node>(); 

            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                {
                    if (grid[i,j] == BUILDING)
                    {
                        Node node = new Node(i, j);
                        list.Add(node);
                    }

                }
            return list;
        }

        /*
         * get shortest distance to all the buildings 
         */
        public int shortestDistance(int[,] grid, int rows, int cols)
        {
            int[,] dist = new int[rows, cols];     // the sum of distance from each building to this position      

            int[,] reach = new int[rows, cols];    // how many buildings can reach the land at position (i,j)       

            // step 1: BFS and calcualte the min dist from each building
            // also, each building will do BFS, and accumulate the value of 
            // dist and reach array - 
            int totalBuildings = getTotalBuildingsCount(grid, rows, cols);
            IList<Node> list = getBuildings(grid, rows, cols);

            foreach (Node node in list)
                BFS(node, dist, reach, grid, rows, cols);

            // step 2: caluclate the minimum distance
            int minDist = Int16.MaxValue;
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    if (grid[i, j] == EMTPYLAND && reach[i, j] == totalBuildings)
                    {
                        int value = dist[i, j];
                        minDist = value < minDist ? value : minDist; 
                    }
                }
            }

            return minDist == Int16.MaxValue ? -1 : minDist;
        }
        
     
        private void BFS(Node origNode,
            int[,] dist,
            int[,] reach,
            int[,] grid, 
            int rows, 
            int cols
            )
        {            
            bool[,] visited = new bool[rows, cols];            

            Queue<Node> queue = new Queue<Node>();

            // add first node into the queue 
            queue.Enqueue(new Node(origNode.x, origNode.y, 0));

            // BFS - visit all nodes in the grid
            while (queue.Count > 0)
            {
                Node node = queue.Dequeue();

                int distance = node.distance;

                int tmpX = node.x;
                int tmpY = node.y; 

                distance++;    // increment one !

                // four directions - breadth first search 
                int[][] directions = {new int[2]{-1,  0},    // left
                                      new int[2]{ 1,  0},    // right
                                      new int[2]{ 0, -1},    // down 
                                      new int[2]{ 0,  1}     // up 
                                     };

                for (int i = 0; i < directions.Length; i++)
                {
                    if (comboCheckings(node, directions[i], grid, visited, rows, cols))
                    {
                        // Let us complete some tasks
                        int neighbor_X = tmpX + directions[i][0];
                        int neighbor_Y = tmpY + directions[i][1];   

                        // alphabetic order 
                        dist[neighbor_X, neighbor_Y] += distance;
                        reach[neighbor_X, neighbor_Y]++;
                        visited[neighbor_X, neighbor_Y] = true;

                        queue.Enqueue(new Node(neighbor_X, neighbor_Y, distance));
                    }
                }
            }
        }

        /*
         *  
         *  Design concern:
         *  BFS - search from a building node, 4 directions. 
         *  
         *  Filter out those 3 cases:
         *  1. The boundary check of matrix is ok 
         *  2. Do not visit more than once
         *  3. Only check empty land node
         *  
         * Ask myself, can this function be more simple? 
         * 4 arguements, but different types, so it is not possible to mix with them. 
         */
        private bool comboCheckings(
            Node     node,
            int[]    direction,
            int[,]   grid,
            bool[,]  visited, 
            int      rows, 
            int      cols)
        {             

            int x = node.x + direction[0];
            int y = node.y + direction[1];

            if (x < 0 || x >= rows || y < 0 || y >= cols)   // boundary check 
                return false;

            if (visited[x, y])      // do not visit the node visited before
                return false;

            if (grid[x, y] != EMTPYLAND)   // only visit empty land 
                return false;

            return true;
        }

        /*   
         * Test case: 
         * 
             1 - 0 - 2 - 0 - 1
             |   |   |   |   |
             0 - 0 - 0 - 0 - 0
             |   |   |   |   |
             0 - 0 - 1 - 0 - 0
         * 
         The point (1,2) is an ideal empty land to build a house, 
         as the total travel distance of 3+3+1=7 is minimal. So return 7.
         * 
         * Ref: jagged array initilization lookup
         * https://msdn.microsoft.com/en-us/library/2s05feca.aspx
       
         */
        static void Main(string[] args)
        {
            int[, ] grid = new int[ 3, 5] { 
                 { 1, 0, 2, 0, 1 }, 
                 { 0, 0, 0, 0, 0 },
                 { 0, 0, 1, 0, 0 } 
            };

            Solution sol = new Solution();

            int result = sol.shortestDistance(grid, 3, 5);
            Console.WriteLine(result);
        }
    }
}