Grid - Breadth First Search (BFS) - II

 Nothing gets more BFS'ish than this problem: Shortest Path to Get Food - LeetCode

1730. Shortest Path to Get Food

Medium

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an m x n character matrix, grid, of these different types of cells:

• '*' is your location. There is exactly one '*' cell.
• '#' is a food cell. There may be multiple food cells.
• 'O' is free space, and you can travel through these cells.
• 'X' is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

 

Example 1:

Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
Output: 3
Explanation: It takes 3 steps to reach the food.

Example 2:

Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
Output: -1
Explanation: It is not possible to reach the food.

Example 3:

Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
Output: 6
Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Example 4:

Input: grid = [["O","*"],["#","O"]]
Output: 2

Example 5:

Input: grid = [["X","*"],["#","X"]]
Output: -1

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[row][col] is '*', 'X', 'O', or '#'.
• The grid contains exactly one '*'.

There is very little to explain: find the start position, using a queue and a hashtable implement a standard BFS (no need for Djikstra here). Code is below, cheers, ACC.

public class FoodQueueItem
{
    public int row = 0;
    public int col = 0;
    public int steps = 0;
    public int key = 0;

    public FoodQueueItem(int maxColRow, int row, int col, int steps)
    {
        this.row = row;
        this.col = col;
        this.steps = steps;

        this.key = row * (maxColRow + 1) + col;
    }
}

public class Solution {
    public int GetFood(char[][] grid)
    {
        //Find me
        int startRow = -1;
        int startCol = -1;
        for (int r = 0; r < grid.Length; r++)
        {
            for (int c = 0; c < grid[r].Length; c++)
            {
                if (grid[r][c] == '*')
                {
                    startRow = r;
                    startCol = c;
                    break;
                }
            }
            if (startRow != -1) break;
        }

        //BFS
        int maxColRow = Math.Max(grid.Length, grid[0].Length);
        Queue foodQueue = new Queue();
        Hashtable visited = new Hashtable();
        FoodQueueItem fqi = new FoodQueueItem(maxColRow, startRow, startCol, 0);
        foodQueue.Enqueue(fqi);
        visited.Add(fqi.key, true);

        while (foodQueue.Count > 0)
        {
            FoodQueueItem cqi = foodQueue.Dequeue();

            if (grid[cqi.row][cqi.col] == '#')
            {
                return cqi.steps;
            }

            int[] rowDelta = { 1, -1, 0, 0 };
            int[] colDelta = { 0, 0, 1, -1 };

            for (int i = 0; i < rowDelta.Length; i++)
            {
                int row = cqi.row + rowDelta[i];
                int col = cqi.col + colDelta[i];

                if (row >= 0 &&
                    row < grid.Length &&
                    col >= 0 &&
                    col < grid[row].Length &&
                    grid[row][col] != 'X')
                {
                    FoodQueueItem nqi = new FoodQueueItem(maxColRow, row, col, cqi.steps + 1);
                    if (!visited.ContainsKey(nqi.key))
                    {
                        visited.Add(nqi.key, true);
                        foodQueue.Enqueue(nqi);
                    }
                }
            }
        }

        return -1;
    }
}