钥匙迷宫

题目描述

33DAI 被困在 Tom 设计的迷宫里。迷宫是一个 $n \times m$ 的网格，每个格子是：

• .：空地，可以走；
• #：墙，不能走；
• S：起点；
• T：出口；
• K：钥匙，走上去就能拿到；
• D：门，拿到钥匙之后才能通过。

33DAI 每步可以走到上下左右相邻的格子。他想知道，从起点到出口最少要走几步。 如果走不到，输出 $-1$。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述迷宫的一行。

输出格式

输出一个整数，表示最少步数；走不到输出 $-1$。

3 3
S..
.#.
..T

4

样例 1 解释

路线：$(1,1) \to (1,2) \to (1,3) \to (2,3) \to (3,3)$，共 $4$ 步。

1 5
S.KDT

4

样例 2 解释

先走到 $(1,3)$ 拿钥匙，再经过 $(1,4)$ 的门，最后到 $(1,5)$，共 $4$ 步。

数据范围

对于所有测试数据，保证：

• $1 \le n, m \le 1000$，$n \times m \le 10^6$；
• 恰好有一个 S 和一个 T；
• K 至多一个，D 可以有多个，其余格子是 . 或 #。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。