7697 - PB - Find YLC   

Description

有三件事情一直讓ylc感到很困擾,第一就是她的方向感奇差,下了公車常常走錯方向,在巷子裡轉超過三個彎一定走不回來,最扯的是念清大三年有時候還是會在宵夜街迷失方向。而且她很不會看地圖,就算有google map也沒用,唯一的優點大概是因此練就了一身問路的本領。每次ylc要出去玩,她的爸媽就會提心吊膽擔心她把自己弄不見。但是今天ylc出門的時候,她沒有把自己弄不見,反而是把回家的鑰匙搞丟了!這就是第二件讓她困擾事:常常弄丟東西。ylc回家需要開三道門,分別需要'Y', 'L', 'C'這三把鑰匙。由於ylc實在太常把鑰匙弄丟,她今天出門就是為了把這三把鑰匙各複製一份,沒想到拿到複製的鑰匙後,還沒回到家,這六把鑰匙就通通被她弄不見了。如果告訴爸媽鑰匙又不見了,爸媽一定會大發雷霆,因此ylc決定她至少要把這三把鑰匙各找回一個。但是她實在是太路癡了沒辦法自己去尋找,所以她發揮了強大的問路本領,請你幫助她。給你一張地圖,有這六把鑰匙所在的位置,你可以告訴ylc她至少需要走多久才可以找回三把鑰匙嗎?ylc可以往上、下、左、右、左上、左下、右上、右下八個方向走,除了以'#'代表的牆壁之外其他的路她都可以走。
噢對了第三件讓ylc困擾的事情就是她很龜毛,她一定要先找到'Y'再找'L'最後才肯去找'C',所以你也必須幫助她按照這個順序找回鑰匙,如果ylc在找到'L'之前就經過'C',她也一定要等到拿到'L'才肯回來拿'C'喔~

Input

有多組測資。
每組測資第一列有兩個數字M, N。代表地圖的大小是M*N。 1<=M, N<=300。
接下來會有M列,每列有N個字元,是地圖的樣子。地圖上只會有5種字元:
'.' : 可以走的路。
'#' : 牆壁,不能走。
'Y' : 'Y'這把鑰匙的位置,每張地圖中都會出現恰好兩次。
'L' : 'L'這把鑰匙的位置,每張地圖中都會出現恰好兩次。
'C' :'C'這把鑰匙的位置,每張地圖中都會出現恰好兩次。

Output

請從任一個'Y'開始,計算ylc要走幾步才能夠走到任一個'L',再走到任一個'C'。
有八種可能的答案,只需要輸出步數最少的那個。
如果ylc可以順利找回三把鑰匙,輸出" YLC can be found in x steps :) ",x是最少所需的步數。
如果ylc沒辦法找回三把鑰匙,輸出" OH NO! YLC can't be found :( "。

Sample Input  Download

Sample Output  Download

Tags




Discuss