Problem D: 拿外卖

Problem D: 拿外卖

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 413  Solved: 52
[Submit] [Status] [Web Board] [Creator:]

Description

智能机器人要帮zser出门拿外卖,zser的家可以看作是一个地图。 
因为外卖小哥急着要去送下一家,所以智能机器人要在规定时间之内出门拿到外卖,外卖小哥在门外等着。
现在我们给出zser家的地图。“S”表示智能机器人现在所在的位置;“#”表示这里不能行走;“.”表示这里是平地,可以通过;“@”表示这里有一堆垃圾挡住了路,需要清理垃圾掉才能通过,而清理垃圾需要的时间为D秒。
zser的家是封闭的(即最外一层都是“#”),而最外层唯一一个不是#的即为大门。
智能机器人每秒只能移动一步,而外卖小哥只等X秒!请你预测下智能机器人能不能取到外卖。

Input

第一行包含四个正整数N,M,D,X,其中N,M表示地图的大小。(3≤N,M≤1000,0≤D≤50,1≤X≤1e6
接下来N行,每行输入M个字符表示zser家的情况。 

Output

智能机器人能取到外卖,输出“Yes”;否则输出“No”。 

Sample Input Copy

4 4 10 3
####
#S.#
##.#
##.#

Sample Output Copy

No