T217571 [FTLOI R1]星火

星星之火，可以燎原。

你是一个傻子。 你在一个 $N × M$ 的草原上。燃起了星星之火，火用 $\verb!#!$ 表示。 当然草原上不止有火，还有水坑，水用 $\verb!*!$ 表示。一个单位的水可以灭一个单位的火，由于你是一个傻子，每次你去水坑只会带走一个单位的水。(尽管你的桶可以装 $v$ 单位大的水) 由于这是星火，所以当你浇灭了这团火后，过了 $1$ 个单位时间它又会燃烧起来（只有一个单位时间的熄灭期）。 你需要走到直升机所在地逃生。 起点用 $\verb!T!$ 表示，直升机所在的用 $\verb!S!$ 表示，草原其他位置用 $\verb!.!$ 表示。 求最小到直升机的步数。如无法到达输出 $-1$。

第一行，三个整数 $N, M, v$。 接下来 $N$ 行，每行 $M$ 个字符

一个整数，表示最小步数

**本题采用捆绑测试** | $\rm Subtask$ 编号 | 分值 | 时间限制 | 特殊限制 | | :----------: | :----------: | :----------: | :----------: | | $0$ | $10$ | $500\ \verb!ms!$ | $v=1$ | | $1$ | $10$ | $500\ \verb!ms!$ | $N,M,v\le30$ | | $2$ | $20$ | $500\ \verb!ms!$ | $N,M\le100$，$v\le200$ | | $3$ | $20$ | $3000\ \verb!ms!$ | $v\le200$ | | $4$ | $40$ | $5000\ \verb!ms!$ | 无特殊限制| 对于 $100 \%$ 的数据， $1\le N,M \le 500$，$1\le v\le 10^9$。 --- 对于**样例一**的解释： 我们可以走以下路径取得最小步数 $8$ $(1, 1) → (2, 1) → (3, 1) → (3, 2) → (2, 2) → (2, 3) → (2, 4) → (2, 5) → (1, 5)$ ### 数据更新日志 - 2022/2/7 ：新增 $2$ 组数据（均为 $1$ pts）,卡掉了部分AC代码