P3869 [TJOI2009] 宝藏

为了寻找传说中的宝藏，小明走进了一个迷宫，我们用一个 $r$ 行 $c$ 列的矩阵来描述这个迷宫，矩阵的每个位置表示一个方块区域： - 字符 `.` 表示可以通过的方格。 - 字符 `#` 表示不能通过的方格。 - 在迷宫中有 $k$ 个机关，第 $i$ 个机关工作方式为： - 每当小明走上第 $r_i$ 行，$c_i$ 列的格子时，位于第 $R_i$ 行，$C_i$ 列的格子改变状态（如果这个格子此时可以通过，此后就变为不能通过；如果此时不能通过，此后可以通过。最左上角的格子是第 $1$ 行第 $1$ 列）。 现给出当前小明的位置，宝藏的位置，迷宫中每个格子的状态，以及所有机关的描述，问小明至少还要走多少步才能拿到宝藏（不能走出迷宫的边界，在开始时刻，小明和宝藏所在的位置都是可以通过的，机关不会出现在起点和终点，也不会影响这两个格子）。

输入数据的第 $1$ 行是两个整数：$r$ 和 $c$。 输入数据的第 $2$ 行到第 $r+1$ 行，每行是一个长度为 $c$ 的字符串，描述迷宫的当前状态：`.` 表示此时可以通过的格子，`#` 表示此时不能通过的格子，`S` 表示起点，`T` 表示宝藏的位置。 输入数据的第 $r+2$ 行是一个整数 $k$，表示机关的数目。接下来有 $k$ 行，每一行包含 $4$ 个整数 $r_i,c_i,R_i,C_i$，用来描述一个机关。

输出一个整数：小明最少需要走多少步才能拿到宝藏。测试数据保证可以找到宝藏。

### 数据范围及约定 对于全部数据，$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$。