Description

To search for the legendary treasure, Xiao Ming enters a maze. We describe this maze with an $r$-by-$c$ matrix, where each position represents a square cell:

• The character . means the cell is passable.
• The character # means the cell is impassable.
• There are $k$ mechanisms in the maze. The $i$-th mechanism works as follows:
  • Whenever Xiao Ming steps onto the cell at row $r_i$, column $c_i$, the cell at row $R_i$, column $C_i$ toggles its state (if that cell is passable at that moment, it becomes impassable afterward; if it is impassable, it becomes passable afterward. The top-left cell is row $1$, column $1$).

Given Xiao Ming’s current position, the treasure’s position, the current state of every cell in the maze, and all mechanism descriptions, determine the minimum number of steps Xiao Ming still needs to reach the treasure (he cannot move outside the maze boundary. At the start, both Xiao Ming’s cell and the treasure’s cell are passable. No mechanism appears at the start or the end, and no mechanism affects these two cells).

Input Format

The first line contains two integers: $r$ and $c$.

Lines $2$ to $r+1$ each contain a string of length $c$, describing the current state of the maze: . means a passable cell, # means an impassable cell, S marks the start, and T marks the treasure’s position.

Line $r+2$ contains an integer $k$, the number of mechanisms. Then $k$ lines follow, each containing $4$ integers $r_i, c_i, R_i, C_i$, describing one mechanism.

Output Format

Output a single integer: the minimum number of steps Xiao Ming needs to reach the treasure. The testdata guarantees the treasure is reachable.

5 5
S.#..
#####
..#..
##.#.
...#T
6
1 5 4 2
1 4 3 3
5 1 3 3
1 4 4 5
1 2 1 3
1 5 2 1

22

Hint

Constraints

For all testdata, $5 \le r, c \le 30$, $0 \le k \le 10$, $1 \le r_i, R_i \le r$, $1 \le c_i, C_i \le c$.

Translated by ChatGPT 5