【问题描述】

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’表示起飞点

【输出】

只输出一个整数，即为最大速度。