#C4665. Robot Maze Navigation

    ID: 48228 Type: Default 1000ms 256MiB

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.

## sample
4 4
B.#.
.#.#
..#T
....
True

</p>