You are given an $m \times n$ character matrix grid, representing a map with the following cell types:

• '*': Your starting position. There is exactly $1$ such cell.

• '#': A food cell. There may be multiple food cells.

• 'O': An empty cell that you can freely walk through.

• 'X': An obstacle that you cannot pass through.

You may move from a cell to any adjacent cell vertically or horizontally (up, down, left, or right) in $1$ step, provided the destination cell is within the bounds of grid and is not an obstacle.

Return the minimum number of steps required to reach any food cell from your starting position. If it is impossible to reach any food cell, return $-1$.

Constraints:

• m == grid.length

• n == grid[i].length

• $1 \leq m, n \leq 200$

• grid[row][col] is '*', 'X', 'O', or '#'.

• The grid contains exactly $1$ '*'.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.