PID502 / [HFOI2005]史莱克
题目描述

怪物史莱克在驴子的帮助下,从喷火龙和暴君手中救出了菲奥娜公主。他也有幸将要成为公主的丈夫。在婚礼前,他偶然得到了一张地图,上面记录了一批宝藏的埋藏地。史莱克很高兴,他想找到这批宝藏,来为自己和菲奥娜公主办一个盛大的婚礼,但是他无法确定是否能到达宝藏的埋藏处,而且能够安全返回。他可不想以自己的生命为代价。所以想请你帮忙编写一个程序告诉他结果,如果你得出能安全到达和返回,史莱克就开始他的寻宝旅程,如果答案是否定的,旅程就只好放弃了。

这个地图由一个一个20km*20km的区域组成。史莱克一天恰好也只能走20km,也就是说在一天之内,他只能从一个区域走到与其上相邻、下相邻、左相邻或者右相邻的区域。由于一些原因,史莱克只能沿着水平或垂直的方向行走。也就是说他不能沿着左上、右上、左下、右下这样的方向前进。

地图上共有6种地形,分别是:沙漠、绿洲、森林、城镇、大路和沼泽。这个地图上也标出了,在各个地形上行走的耗水量。当走在大路上时,一天需要消耗2kg的水,在森林里,一天只要消耗1kg的水,因为树木会遮挡阳光。当穿越绿洲时,根本就不需要消耗水,因为在绿洲里,如果渴了,随时都能够发现水。如果穿越沙漠,那么一天的耗水量就要上升到4kg。在旅途中到达一个城镇是非常幸运的事情,因为,城镇里好客的人们不但会款待史莱克,而且还能够为他最大限度的补充水。但是,如果遇到沼泽地,最好还是小心,因为那里每走一步都要面临死亡的威胁,史莱克可不想冒这样的险,所以,遇到沼泽就意味着无法穿越。在旅途中,如果所带的水没有了,史莱克就不能继续他的旅程了。

在地图上用S表示出发点,T表示宝藏埋藏点,D表示沙漠,O表示绿洲,F表示森林,C表示城镇,R表示大路,M表示沼泽。所以地图可能是下面这个样子:

RRRRRRRRRRRRRRR

RRSRRRFFFFFFFFF

DDDDDDDDFFFFFFF

DDDDODDDFFFFFFF

DDDDDDCDFFFFFFF

DTDDOOOOFFFFFFF

RRRRRRRRRRRRRMM

对于出发点和宝藏埋藏点,它们被看成和大路一样,也就说出发时要消耗2kg的水,返回的时候,也要在宝藏埋藏点消耗2kg的水。挖掘宝藏时,消耗的时间是很少的,所以不会消耗水。

史莱克会告诉你他最多能带多少水。现在就要求你,给他一个结果,到底能不能开始他的旅程。如果可以开始的话,你要告诉他当他回到出发点的时候,他最多还能剩余多少的水。因为离他的婚礼还有充足的时间,所以他关心最后最多能剩余多少水超过旅程所花的时间。

注意:如果在旅途中史莱克所带的水降为0,如果这时候他在城镇里,他依然可以继续他的旅程,因为在那他可以得到足够的补给;如果他在绿洲里,他可以继续走进相邻的绿洲(如果有相邻的绿洲),因为在绿洲里行走不需要消耗水;如果他在别的地形中,他只能放弃他的旅程了。

输入格式

第一行有一个非负整数W(0<=W<=1000),表示史莱克所能带的最大水量。下面一行有两个整数m、n(0<m,n<1000),标明了地图的尺寸,m表示一行有多少个20km*20km的区域,n表示有多少行。紧接着n行,每行有m个字符,描述了地图的地形,里面也包括了一个S(出发点)和一个T(宝藏埋藏处)。

输出格式

如果史莱克能够到达宝藏埋藏点,并且能够安全返回,那么,首先在第一行输出Yes,然后换行输出最后最多能剩余的水量。如果不能开始旅程,那么就输出No。(注意Yes和No,首字母要大写)

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论