Minimum Steps for Robots in a Grid

In this problem, you are given an N x M grid representing a map. Each cell is either passable, denoted by ., or blocked, denoted by #. You are also given K robots. For each robot, you are given its starting position and its destination. Robots can move one cell at a time in one of the four directions: up, down, left, or right. The goal is to compute the minimum number of steps required for each robot to reach its destination. If it is impossible for a robot to reach the destination, output -1 for that robot.

The problem is solved using a Breadth-First Search (BFS) algorithm. In BFS, each move increases the step count by 1. Formally, the update is given by $$\text{steps}_{next} = \text{steps}_{current} + 1.$$

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers N and M (the number of rows and columns respectively).
2. The next N lines each contain a string of M characters representing the grid.
3. The following line contains an integer K representing the number of robots.
4. Each of the next K lines contains four integers: sx sy ex ey, representing the starting and ending positions (0-indexed) of a robot.

outputFormat

Output a single line to standard output (stdout) consisting of K space-separated integers. The i-th integer should be the minimum number of steps required for the i-th robot to reach its destination; output -1 if it is impossible.

5 5
.....
.###.
.#.#.
.###.
.....
2
0 0 4 4
2 2 0 0

8 -1