U25362.国王的食物半成品

从前，有一个美丽的国度，人们安居乐业，国王非常喜欢一种食物，而这种食物的原材料在国度的天涯海角，现在告诉你原材料位置与出发点，问最短要走多长的路(不用计算返程路程)

第一行两个数字$n,m$代表国度的长宽单位：光年(bushi)
然后$n$行，每行$m$个字符，形容国度的土地
#表示山巅或山谷，你无法穿过
.表示平地，你可以走在上面
$表示原材料
*表示出发地
你必须要收集所有材料才可以给国王交代

输出分两行
第一行如果可以收集所有材料输出1反之为0
第二行如果可以收集所有材料输出最短路径
否则输出最多能拿到的材料数量

(1<=n,m<=30)
(2<=$的数量<=40)