小碘梦游来到某一个不知名的平行空间,这里危机四伏。他刚准备逃离这里,突然他看到美丽的公主也被困在了这里,19年单身的他觉得这是一个好机会,于是他想带着这位公主一起逃生。但是公主表示,她懒癌犯了,不想动。所以小碘只能先去接公主然后一起逃生。
丘比特看到这个场景之后狂喜,因为它又可以磕cp了,它准备利用它能飞的技能给小碘画张地图,这样能帮助小碘逃离这里。丘比特环绕一周后发现这里既有怪兽栖息地,出去觅食的怪兽还有坑坑洼洼的水坑。公主虽然高傲,但也愿意和他一起踩水坑,所以小碘只需要绕开怪兽栖息地和出去觅食的怪兽就行了。
这是一张n*m的地图,'&'表示怪兽栖息地,'$'表示怪兽,'@'表示水坑。其他平地用'#'表示。地图中'D'表示小碘的位置,'P'表示公主的位置。小碘每次只能在自己的位置往上下左右四个位置走一格,每走一格他需要花费1s。在救出公主之前他不能离开地图的边界,因为这样他就会梦醒了。他需要用最短的时间带着公主逃离这里(即最优解)。
只要小碘带着公主逃离这张地图,即离开地图的边界就算成功,成功之后他就会发现自己梦醒了。如果他无法救出公主,或者不能带公主离开,他也会醒来,然后emo了,说一句:”失去你,活着又如何?“。
第一行输入两个整数n,m表示这张地图的大小。
接下来n行,每行输入m个字符,表示这张地图的情况。
如果小碘能成功带着公主逃离,你需要告诉他,他做梦做了多少秒。如果他做梦做了10秒,则输入"You woke up at 10 seconds"(引号不需要输出)
如果小碘无法救出公主,或者不能带公主离开,则输出"What is life without you"(引号不需要输出)