在一片 n 行 m 列的网格空地上,散落着若干块水晶。网格里的每个格子要么是可以通行的空地,要么是无法穿越的岩石。
你从起点 S 出发,每一步可以向上、下、左、右移动到相邻的格子,既不能走出网格,也不能踏入岩石格。你需要收集到全部水晶,收集的先后顺序可以任意安排,最后停在终点 T。
请计算最少需要走多少步。如果无论怎么走都无法收集全部水晶并到达终点,输出 -1。
第一行,两个整数 n、m,分别表示网格的行数和列数。
接下来 n 行,每行是一个长度为 m 的字符串,描述这一行的 m 个格子。字符串中只可能出现下面五种字符:. 表示空地,# 表示岩石,S 表示起点,T 表示终点,* 表示一块水晶。
保证整个网格中恰好有一个 S 和一个 T,水晶的颗数记为 k。
输出一个整数,表示收集全部水晶并到达终点所需的最少步数;若无法做到,则输出 -1。
3 4 S..* .##. ...T
5
对于所有测试数据,都保证:
1 ≤ n, m ≤ 2000
0 ≤ k ≤ 8
对于部分测试点具体数据描述如下:
测试点 1~3(30 分):k = 1,n, m ≤ 100。
测试点 4~7(40 分,累计 70 分):k ≤ 3,n, m ≤ 500。
测试点 8~10(30 分,累计 100 分):k ≤ 8,n, m ≤ 2000。