#C4665. Robot Maze Navigation
Robot Maze Navigation
Robot Maze Navigation
You are given a maze represented as a grid of M rows and N columns. Each cell of the grid contains one of the following characters:
- B: the starting position of the robot.
- T: the target position the robot needs to reach.
- .: an empty cell through which the robot can pass.
- #: a blocked cell that the robot cannot traverse.
The robot can move in four directions: north, south, east, and west. Your task is to determine whether the robot can reach the target from its starting position without passing through any blocked cells.
The movement can be mathematically expressed using the following formula for a move from cell \((x,y)\) to \((x+dx, y+dy)\):
\[ (x,y) \to (x+dx, y+dy), \quad \text{where} \quad (dx,dy) \in \{(-1,0), (0,1), (1,0), (0,-1)\} \]Use a breadth-first search (BFS) strategy to solve the problem.
inputFormat
The first line contains two integers M and N separated by a space, representing the number of rows and columns of the grid respectively.
The following M lines each contain a string of N characters. The characters are one of 'B', 'T', '.', or '#'.
outputFormat
Output a single line: True
if the robot can reach the target position, and False
otherwise.
4 4
B.#.
.#.#
..#T
....
True
</p>