using System;
using System.Linq;

namespace Amazon
{
    class Program
    {
        //23280666352337
        static void Main(string[] args)
        {


        }

        public int numberAmazonGoStores(int rows, int column, int[,] grid)
        {

            // store the already visited rows and column
            var visited = new int[rows, column];

            int numberOfBuildings = 0;

            // iterate through all rows and columns to get number of buildings that Amazon can open stores in
            for (int currentRow = 0; currentRow < rows; currentRow++)
            {

                for (int currentCol = 0; currentCol < column; currentCol++)
                {

                    numberOfBuildings += getNumberOfBuildings(grid, currentRow, currentCol, visited);
                }
            }

            return numberOfBuildings;

        }


        int getNumberOfBuildings(int[,] grid, int row, int col, int[,] visited)
        {


            if ((!isValid(grid, row, col)) || grid[row, col] == 0 || visited[row, col] == 1)
            {
                return 0;
            }

            visited[row, col] = 1;
            // recursively go through the grid horizontally and vertically to find connected 1's
            getNumberOfBuildings(grid, row, col + 1, visited);
            getNumberOfBuildings(grid, row, col - 1, visited);
            getNumberOfBuildings(grid, row + 1, col, visited);
            getNumberOfBuildings(grid, row - 1, col, visited);

            return 1;
        }

        // checks if the requested positon is within bounds of the array
        bool isValid(int[,] grid, int row, int col)
        {

            int rows = grid.GetLength(0);
            int cols = grid.GetLength(1);

            return row >= 0 && row < rows && col >= 0 && col < cols;
        }

    }

public class Solution2
    {
        // METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
        public int minimumHours(int rows, int columns, int[,] grid)
        {
            return CalculateHours(rows, columns, grid);
            // WRITE YOUR CODE HERE
        }


        private int CalculateHours(int rows, int columns, int[,] grid)
        {
            Queue<int[]> queue = new Queue<int[]>();

            // total number of servers
            int target = rows * columns;

            int count = 0, res = 0;

            // iterate through all the rows and columns
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    // if the current server has already received the file, add it to the queue
                    if (grid[i, j] == 1)
                    {
                        queue.Enqueue(new int[] { i, j });
                        count++;
                    }
                }
            }

            //  directions: vertical: down and up, horizontal: left and right
            int[][] direction = GetDirections();

            //Check for queue not empty
            while (queue.Count != 0)
            {
                int size = queue.Count;

                if (count == target)
                    return res;

                for (int i = 0; i < size; i++)
                {
                    int[] cur = queue.Dequeue();

                    // check all four directions: left, right, up, down
                    // send files to ajdacent servers and set the server status to 1
                    foreach (var dir in direction)
                    {
                        int ni = cur[0] + dir[0];
                        int nj = cur[1] + dir[1];
                        // check if the current direction is valid and within bounds
                        if (ni >= 0 && ni < rows && nj >= 0 && nj < columns && grid[ni, nj] == 0)
                        {
                            count++;
                            queue.Enqueue(new int[] { ni, nj });
                            grid[ni, nj] = 1;
                        }
                    }
                }

                res++;
            }

            return -1;
        }

        //  directions: vertical: down and up, horizontal: left and right
        int[][] GetDirections()
        {
            int[][] direction = new int[4][];

            direction[0] = new int[] { 0, 1 };
            direction[1] = new int[] { 0, -1 };
            direction[2] = new int[] { 1, 0 };
            direction[3] = new int[] { -1, 0 };

            return direction;
        }

    }