Leetcode discuss: 1162. As Far from Land as Possible

March 21, 2022

Here is the link. 

C# | BFS | All land nodes into Queue | Search together

March 21, 2022
Introduction
The algorithm is to ask a water node's maximum distance from land node. The idea is to put all land nodes into a queue, and then apply BFS search to visit all water nodes. The steps to run into an empty queue is that the steps to find maximum water node in given matrix.

The following C# code passes online judge.

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

namespace _1162_far_from_land
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// code study
        /// https://leetcode.com/problems/as-far-from-land-as-possible/discuss/1096186/c
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int MaxDistance(int[][] grid)
        {
            if (grid == null || grid.Length == 0)
            {
                return 0;
            }

            int result = -1;
            var queue = new Queue<int[]>();
            var rows = grid.Length;
            var columns = grid[0].Length;

            var visited = new bool[rows, columns];

            var directionRow = new int[] { 0, 0, 1, -1 };
            var directionColumn = new int[] { 1, -1, 0, 0 };

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    if (grid[i][j] == 1)
                    {
                        queue.Enqueue(new int[] { i, j });
                    }
                }
            }

            // apply BFS search
            while (queue.Count > 0)
            {
                var count = queue.Count;

                result++;

                while (count > 0)
                {
                    var current = queue.Dequeue();

                    for (int direction = 0; direction < 4; direction++)
                    {
                        int nextRow = current[0] + directionRow[direction];
                        var nextColumn = current[1] + directionColumn[direction];

                        if (nextRow > -1 && nextRow < grid.Length && nextColumn > -1 && nextColumn < grid[0].Length && !visited[nextRow, nextColumn] && grid[nextRow][nextColumn] == 0)
                        {
                            queue.Enqueue(new int[] { nextRow, nextColumn });
                            visited[nextRow, nextColumn] = true;
                        }
                    }

                    count--;
                }
            }

            return result == 0 ? -1 : result;
        }
    }
}