Minimum Moves to Point of Interest

Given an n×m grid, determine the minimal number of moves required to reach the nearest point of interest (denoted by '') from a given starting position. The grid consists of three types of characters: . represents an empty cell, # represents an obstacle, and </code> denotes a point of interest. Movements are allowed in the four cardinal directions: up, down, left, and right. If a point of interest is not reachable, output -1.

The distance is defined as the number of moves taken. Mathematically, if we denote the moves by (d), then our goal is to find the minimum (d) such that:

[ d = \min{\text{number of moves from } (sx, sy) \text{ to any cell } (i,j) \text{ with } grid[i][j]='*'}. ]
Use a breadth-first search (BFS) algorithm to solve this problem.

inputFormat

The first line contains a single integer t, the number of test cases. For each test case, the input format is as follows:

1. The first line contains four integers n, m, sx, and sy separated by spaces. Here, n is the number of rows, m is the number of columns, and ((sx, sy)) is the starting position (0-indexed).
2. Followed by n lines, each line contains a string of length m representing the grid. Each character is either . (empty cell), # (obstacle), or * (point of interest).

outputFormat

For each test case, print a single integer on a new line representing the minimal number of moves required to reach a point of interest ('*') from the starting position ((sx, sy)). If it is impossible to reach any point of interest, output -1.## sample

3
3 3 0 0
..*
.#.
.*.
3 3 0 0
..#
.#.
.#.
1 1 0 0
*

2
-1
0