PID97 / 最大速度
题目描述

【问题描述】

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

输出格式

【输出】

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

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