1091. Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix C# breadth first search practice in 2019

Breadth first search practice in 2019

It is a medium level algorithm. I came out the idea to use queue to do breadth first search, and also mark visited node in case of deadloop.

The problems I came cross are the following:

1. Read the statement carefully. I think that it should say explicitly that all nodes on the path should have value 0.
2. Minimum path should also be defined clearly. Count nodes not edges.

I think that the example 2 in problem statement should include a picture to show the path instead of just showing 4 as a result. In the contest, I could not figure out why it is 4. I draw the diagram in the following:

The above example 2 the minimum path is 4. So it is counting how many nodes on the path.

Here are highlights:

1. Design a data structure to store values in Queue, int[] is a good choice. I like to explicitly pass level to express minimum steps from (0,0) to the node;
2. Breadth first search, I like to apply search one level a time. All next level nodes are saved in the queue first;
3. Mark visited nodes using original matrix grid to avoid deadloop.

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

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

        /// <summary>
        /// 1091 Shortest path binary matrix 
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public static int ShortestPathBinaryMatrix(int[][] grid)
        {
            if (grid == null || grid.Length == 0 || grid[0].Length == 0)
                return -1;

            var rows = grid.Length;
            var columns = grid[0].Length;

            if (grid[0][0] != 0 || grid[rows - 1][columns - 1] != 0)
                return -1;

            var queue  = new Queue<int[]>();

            var numbers = new int[] { 0, 0, 1 };
            queue.Enqueue(numbers);
            var maxLength = -1;
            
            // apply BFS, put next level into the queue, 8 possible neighbors
            applyBFS(grid, rows, columns, queue, ref maxLength);

            return maxLength;
        }

        /// <summary>
        /// visit neighbor with value 0, eight neighbors
        /// using breadth first search, use Queue
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="rows"></param>
        /// <param name="columns"></param>
        /// <param name="queue"></param>
        /// <param name="maxLength"></param>
        /// <returns></returns>
        private static void applyBFS(int[][] grid, int rows, int columns, Queue<int[]> queue, ref int maxLength)
        {
            if (queue.Count == 0)
                return;
            
            while (queue.Count > 0)
            {
                var count = queue.Count;
                int index = 0;

                while (index < count)
                {
                    var numbers = queue.Dequeue();
                    var row    = numbers[0];
                    var column = numbers[1];                    
                    var level  = numbers[2];                                      
                    
                    if (row == rows - 1 && column == columns - 1)
                    {
                        maxLength = level;
                        break;
                    }

                    var nextLevel = level + 1; 
                    // put 8 neighbors into queue
                    visitNeighbors(grid, rows, columns, row,     column - 1, queue, nextLevel);  // left
                    visitNeighbors(grid, rows, columns, row,     column + 1, queue, nextLevel);  // right
                    visitNeighbors(grid, rows, columns, row - 1, column,     queue, nextLevel);  // up
                    visitNeighbors(grid, rows, columns, row + 1, column,     queue, nextLevel);  // down
                    visitNeighbors(grid, rows, columns, row - 1, column - 1, queue, nextLevel);  // left top
                    visitNeighbors(grid, rows, columns, row + 1, column + 1, queue, nextLevel);  // right down
                    visitNeighbors(grid, rows, columns, row + 1, column - 1, queue, nextLevel);  // right top
                    visitNeighbors(grid, rows, columns, row - 1, column + 1, queue, nextLevel);  // left down

                    index++;
                }
            }
        }

        /// <summary>
        /// mark visited using -1 and save the value in grid matrix
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="rows"></param>
        /// <param name="columns"></param>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <param name="queue"></param>
        /// <param name="level"></param>
        private static void visitNeighbors(int[][] grid, int rows, int columns, int row, int column, Queue<int[]> queue, int level)
        {
            if (row < 0 || row >= rows || column < 0 || column >= columns || grid[row][column] < 0 || grid[row][column] != 0)
                return;

            var numbers = new int[] { row, column, level };

            grid[row][column] = -1; // mark visited

            queue.Enqueue(numbers); 
        }
    }
}