失去你,活着又如何?
题号:NC229743
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述


        小碘梦游来到某一个不知名的平行空间,这里危机四伏。他刚准备逃离这里,突然他看到美丽的公主也被困在了这里,19年单身的他觉得这是一个好机会,于是他想带着这位公主一起逃生。但是公主表示,她懒癌犯了,不想动。所以小碘只能先去接公主然后一起逃生。

        丘比特看到这个场景之后狂喜,因为它又可以磕cp了,它准备利用它能飞的技能给小碘画张地图,这样能帮助小碘逃离这里。丘比特环绕一周后发现这里既有怪兽栖息地,出去觅食的怪兽还有坑坑洼洼的水坑。公主虽然高傲,但也愿意和他一起踩水坑,所以小碘只需要绕开怪兽栖息地和出去觅食的怪兽就行了。

        这是一张n*m的地图,'&'表示怪兽栖息地,'$'表示怪兽,'@'表示水坑。其他平地用'#'表示。地图中'D'表示小碘的位置,'P'表示公主的位置。小碘每次只能在自己的位置往上下左右四个位置走一格,每走一格他需要花费1s。在救出公主之前他不能离开地图的边界,因为这样他就会梦醒了。他需要用最短的时间带着公主逃离这里(即最优解)。

        只要小碘带着公主逃离这张地图,即离开地图的边界就算成功,成功之后他就会发现自己梦醒了。如果他无法救出公主,或者不能带公主离开,他也会醒来,然后emo了,说一句:”失去你,活着又如何?“。


输入描述:

第一行输入两个整数n,m表示这张地图的大小。

接下来n行,每行输入m个字符,表示这张地图的情况。

输出描述:

如果小碘能成功带着公主逃离,你需要告诉他,他做梦做了多少秒。如果他做梦做了10秒,则输入"You woke up at 10 seconds"(引号不需要输出)

如果小碘无法救出公主,或者不能带公主离开,则输出"What is life without you"(引号不需要输出)

示例1

输入

复制
4 4
#@#@
#P$#
$&$#
D###

输出

复制
You woke up at 11 seconds

说明

小碘营救路线(4, 1)->(4,2)->(4,3)->(4,4)->(3,4)->(2,4)->(1,4)->(1,3)->(1,2)->(2,2)->(2,1)->逃离