Push a Box

This problem is adapted from USACO 2017 December Contest, Platinum Problem 2. Push a Box.

A barn is represented as an \(N \times M\) rectangular grid. Some cells contain hay bales. Bessie starts in one cell and there is a large wooden box in another cell. Bessie cannot occupy a cell with hay or a cell with the box.

Bessie is allowed to move in the four cardinal directions (north, south, east, and west) provided that the destination cell does not contain hay. If she attempts to move into the cell containing the box, she pushes the box one cell in the same direction, as long as that cell exists and is not blocked. Otherwise, she cannot move.

Given the layout of the barn (with empty cells, hay bales, and the initial placement of the box), Bessie's starting position, and the target cell where the box must be pushed, determine whether it is possible for Bessie to push the box to the target cell.

The movement of Bessie and the box follows these rules:

• Bessie can move to an adjacent cell (up, down, left, or right) if it is within bounds and does not contain hay.
• If the adjacent cell contains the box, then the box is pushed one cell further in the same direction provided that the destination cell for the box is within bounds and does not contain hay.
• At each step, the state is determined by Bessie's position and the box's position. The goal is to reach a state where the box is at the target cell.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns of the grid.

The following \(N\) lines each contain a string of length \(M\) describing the grid. The characters in the grid are as follows:

• B : Bessie's starting position (appears exactly once)
• O : The initial position of the box (appears exactly once)
• T : The target position for the box (appears exactly once)
• # : A cell containing a hay bale
• . : An empty cell

outputFormat

Output YES if it is possible for Bessie to push the box to the target position, otherwise output NO.

sample

3 3
B..
.O.
..T

YES