s02189. 限步脱困 未做

一个 $n\times m$ 的地牢，. 是空地、# 是墙、S 是起点、T 是出口、* 是检查点（至少一个）。从 $S$ 出发，每步可以向上、下、左、右走一格（不能穿墙、不能越界），要求经过所有检查点（顺序任意）、不能重复经过同一格，最后停在 $T$。问是否存在总步数不超过 $k$ 的路线。

第一行三个整数 $n,m,k$。接下来 $n$ 行，每行 $m$ 个字符。

存在这样的路线输出 YES，否则输出 NO。

• 对于 30% 的数据：$n,m\le 4$，检查点不超过 2 个
• 对于 60% 的数据：$n,m\le 5$，检查点不超过 3 个
• 对于 100% 的数据：$n,m\le 6$，检查点不超过 4 个，$k\le 40$