SEA405 钥匙迷宫

难度梯度：T4-｜训练重点：BFS 扩展状态：位置+钥匙集合

题目描述

地图中 S 为起点，T 为终点，. 可走，# 为墙，a～f 是钥匙，A～F 为对应门。进入钥匙格会永久获得该钥匙，进入门格须先持有对应钥匙。求走到 T 的最少步数，不可达输出 -1。

拿到某种钥匙后可无限次经过对应门；钥匙不会被门消耗。同一种钥匙可以再次经过，但状态仍表示“已拥有”。

输入格式

第一行 N M，随后 N 行地图；地图中恰有 S 和 T。

输出格式

输出最少步数或 -1。

样例输入

2 4
SaAT
####

样例输出

3

样例说明

先取得 a，再通过 A 到 T。

数据范围

1≤N,M≤20；只出现 a～f、A～F。

子任务

20 分：无钥匙和门；30 分：仅一类钥匙；50 分：无附加限制。