题目描述
【问题描述】
Ron的老爸的Flying Car出了些问题,现在必须要在地上跑到很大的速度才能飞起来,但是Flying Car飞起来的那一刻不能被麻瓜看到。为了确保安全飞起来,需要知道车到可以飞起来的地方时所能达到的最大速度。他的Flying Car一开始拥有一个初速度,移动一次增加速度1;因为车道很窄,宽度只有1,所以仅当要转向的方向有路时才能转,左转一次减少速度35,右转一次减少速度40,当前进、左转、右转都无路可走的时候,调头(连左转两次或连右转两次也认为是调头)才可以,调头每次速度变为0;速度不会小于0,如果当前速度小于等于要减少的速度,则减少速度为0。
给出一张地图,取向上为北方,要求你求出从起始点到达起飞点时速度最大的路径。幸运的是,所有的道路都是正北、正南、正西或正东方向的。只有一个起点、一个起飞点,他们之间总存在可通达的路径。同时由于地图周围一圈均是障碍区,所以Flying Car是没有可能开出道路的。
出自:宜昌一中
输入格式
【输入】
(1)第一行有3个整数,地图高度h、宽度w和初速度v。
(2)其后h行每行w个字母,将是以下字母中的一个:
‘.’表示障碍区
‘#’表示道路
‘E’表示起始点且Flying Car面朝东
‘W’表示起始点且Flying Car面朝西
‘N’表示起始点且Flying Car面朝北
‘S’表示起始点且Flying Car面朝南
‘F’表示起飞点
输出格式
【输出】
只输出一个整数,即为最大速度。
样例输入
样例输出