The Real GTA Grand Theft Auto (Bonus, 20 Points)

AI悦创原创大约 13 分钟...约 3780 字

1. Background

I can’t take anymore! You know what I am saying? This is bllsht! Those cops should write those dumb codes themselves.

Franklin said to himself. He attempted to break out of the LSPD holding cell the old-fashioned way - knocking out the guards and grabbing the keys. Just walking to the door, he was knocked down and sent back to the dim cell by the backup police officers who heard the sirens.

He suddenly remembers Leslie, the cripple he used to work with. He finds a way to get in touch with Leslie. Leslie says he can get Franklin out, but he needs Franklin to do what he says.

One day, Franklin finds a note in his lunch bread. The note tells him to rob the escort vehicle and escape on his way back to his cell from the office. Sure enough, in the afternoon Franklin got into the escort vehicle. On the way, the guard said he wanted a burger from McDonald’s, so he put a hook on Franklin’s head and cuffed his hands to the steering wheel.

To Franklin’s surprise, Leslie’s voice came over the radio. He told Franklin to drive the car right now.

I got mad respect for you man. But I can’t see anything, bro. I can’t even take off this dumb hood. Franklin said.

If you are still eager for freedom, do as I say! Stupid! Leslie roared.

2. Description

Franklin has to drive to the safe house within the time limit. Since Franklin’s head is covered by a hood and his hands are tied up, all he can do is step on the gas, hit the brakes and change the direction. Not only that, he doesn’t know the location of the safe house so he has to follow Leslie’s directions. Luckily, the main roads in Los Santos were basically straight, so with Franklin’s excellent driving skills he could estimate the distance of a block.

Leslie knows the size of the map, which is rectangular in shape, Leslie also creates a simple coordinate system. The point at the bottom left corner is the origin point (0, 0). He also knows Franklin’s initial location and the location of the safe house. Hearing the siren, Leslie tells Franklin there must be some obstacle on the road, Franklin should avoid hitting the obstacle if he does not want to be arrested again.

The following definitions are given for clarity.

2.1 Direction and Speed

Franklin has an excellent sense of direction and can sense whether he is facing east or south or west or north. Note that speed is a non-negative integer. Note that before receiving the first instruction, Franklin’s speed is always 0.

  • Facing north: (in the absence of obstacles) the next time step Franklin’s vertical coordinate increases by the current speed.
  • Facing south: (in the absence of obstacles) the next time step Franklin’s vertical coordinate decreases by the current speed.
  • Facing east: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate increases by the current speed.
  • Facing west: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate decreases by the current speed.

2.2 Time and Instructions

for a time limit t, the process has t time steps. Franklin always receives t instructions. Some instructions may lead to Franklin’s attributes (direction and speed) change. Instructions contain:

  • North: May change the direction and the speed.
  • South: May change the direction and the speed.
  • East: May change the direction and the speed.
  • West: May change the direction and the speed.
  • Park: Keep the direction and reset the speed.
  • Keep: Keep the direction and the speed.

2.3 Rules for the Game

  1. Rules for Franklin’s Actions:
    • Speed Adjustment Rules
      • When the command direction matches Franklin’s current direction, his speed increases by 1.
      • When the command direction and Franklin’s current direction are at 180-degree angles from each other, his speed decreases by 1 and his direction stays still.
    • Direction Adjustment Rule
      • When the command direction and Franklin’s current direction are at 90-degree angles from each other, his speed remains the same, but his direction changes to the command direction.
    • Zero Speed Rule
      • If Franklin’s speed reaches zero, his direction always changes to the command direction, and his speed is set to 1.
  2. Attribute Precedence
    • Franklin’s attribute changes take precedence over coordinate changes. He first receives instruc- tions that may change his attributes (speed or direction), and then he moves according to the present direction and speed.
  3. Obstacles and Border Rules:
    • When Franklin encounters police-imposed obstacles on the road, he cannot drive through them. These obstacles keep Franklin one block away from the obstacle and change his speed to 0.
    • Franklin cannot pass the borders of the map. If he reaches or attempts to pass the borders, his speed will change to 0.
  4. End of Driving
    • Franklin’sdriveendseitherafteraspecifiednumberoftimesteps(ttimesteps)orwhenhiscoordi- nate is the same as the coordinate of the safe house. In the latter case, the safe house’s coordinates may either match Franklin’s new coordinates after following the instructions or be situated on the path between Franklin’s old and new coordinates.
    • If Franklin’s drive ends, he will disregard all subsequent instructions.

3. Input Format

The input contains 5 lines.

The first line contains three positive integers n, m and t representing the size of the mapping matrix and time limit, where n is the length in the horizontal direction and m is the length in the vertical direction. The integers are separated by one space. The origin point is (0, 0).

The second line is one coordinate of the form (x, y), which is the coordinate of the safe house.

The third line is one coordinate of the form (x, y), which is Franklin’s initial coordinate.

The fourth line is k coordinates of the form (x, y). These coordinates are the coordinates of the obstacle. If there is no obstacle, the input is (−1, −1).

The fifth line is a series of Franklin’s actions including t capital letters: N, E, S, W, P, and K for north, east, south, west, park and keep, respectively.

4. Output Format

The output contains only one integer, indicating the Manhattan Distance between Franklin’s final coordi- nates and the safe house.

5. Test

5.1 test1

Sample Input 1:

3 1 8 

Sample Output 1:


5.2 test2

Sample Input 2:

3 3 4

Sample Output 2:


5.3 test3

Sample Input 3:

3 3 10 

Sample Output 3:


6. Data Constraints

To solve this problem you have to consider a lot of constraints and read the problem thoroughly. However, it is promised that some test cases are easier to handle. The test cases are given as follows:

For the 1st and 2nd test cases, i.e. 1.inopen in new window and 2.inopen in new window:

  • The game map is a single row, i.e. the car can’t move vertically.
  • You may simply ignore all the instructions asking you to move N/S.
  • Note that the car can still face North or South. This may affect it’s speed.

For the 1st-4th test cases, i.e. 1.inopen in new window, 2.inopen in new window, 3.inopen in new window and 4.inopen in new window,

  • No obstacles are given;
  • You can assume that the car won’t hit obstacles;
  • But, be careful to handle it if the car hits the wall!

For another 20% data, i.e. 5.inopen in new window and 6.inopen in new window,

  • They are corner cases;
  • If you get the Wrong Answer on these two test cases, check your code carefully if it works correctly in special cases.

For all test cases, 1n1 \leq n, m64m \leq 64; 1t321 \leq t \leq 32; Let oo be 12(m+n)\frac{1}{2}(m + n), then 1kologo1 \leq k \leq o \log o.

7. Hint

  • Note that there are some police-imposed obstacles on the road. When Franklin encounters these obstacles he cannot drive through them.
  • Note that Franklin can not pass the borders of the map.
  • You do NOT have to figure out why k is constrained as this.

8. 中文

8.1 Background








8.2 Description




8.3 方向与速度


  • 面向北方:(在没有障碍物的情况下)下一个时间步骤富兰克林的垂直坐标将增加当前的速度。
  • 面向南方:(在没有障碍物的情况下)下一个时间步骤富兰克林的垂直坐标将减少当前的速度。
  • 面向东方:(在没有障碍物的情况下)下一个时间步骤富兰克林的水平坐标将增加当前的速度。
  • 面向西方:(在没有障碍物的情况下)下一个时间步骤富兰克林的水平坐标将减少当前的速度。

8.4 时间与指令

对于时间限制 t,过程有 t 个时间步。富兰克林总是会接收到 t 条指令。一些指令可能会导致富兰克林的属性(方向和速度)发生变化。指令包含:

  • 北方:可能会改变方向和速度。
  • 南方:可能会改变方向和速度。
  • 东方:可能会改变方向和速度。
  • 西方:可能会改变方向和速度。
  • 停车:保持方向并重置速度。✅
  • 保持:保持方向和速度。✅

8.5 游戏规则

  1. 富兰克林行动的规则:
    • 速度调整规则
      • 当命令方向与富兰克林当前方向匹配时,他的速度增加1。✅
      • 当命令方向与富兰克林当前方向成180度角时,他的速度减少1,但方向保持不变。✅
    • 方向调整规则
      • 当命令方向与富兰克林当前方向成90度角时,他的速度保持不变,但方向改变为命令方向。✅
    • 零速规则
      • 如果富兰克林的速度降到零,他的方向总是改变为命令方向,并且速度设为1。「考虑」
  2. 属性优先级
    • 富兰克林的属性变化优先于坐标变化。他首先接收可能改变其属性(速度或方向)的指令,然后按照当前方向和速度移动。「考虑」
  3. 障碍物与边界规则:
    • 当富兰克林在路上遇到警方设置的障碍物时,他不能驶过。这些障碍物使富兰克林在障碍物周围保持一定距离,并将他的速度改为0。✅
    • 富兰克林不能越过地图的边界。如果他到达或试图越过边界,他的速度将变为0。✅
  4. 驾驶结束
    • 富兰克林的驾驶在经过指定数量的时间步后结束(t 个时间步),或者当他的坐标与安全屋的坐标相同时结束。在后一种情况下,安全屋的坐标可以与富兰克林按指令后的新坐标相匹配,或位于富兰克林的旧坐标和新坐标之间的路径上。
    • 如果富兰克林的驾驶结束,他将忽略所有后续指令。

8.6 输入格式

输入包含 5 行。

第一行包含三个正整数n、m和t,代表映射矩阵的大小和时间限制,其中n是水平方向的长度,m是垂直方向的长度。整数之间用一个空格分隔。原点坐标为(0, 0)。

第二行是形式为(x, y)的一个坐标,这是安全屋的坐标。

第三行是形式为(x, y)的一个坐标,这是富兰克林的初始坐标。

第四行是k个形式为(x, y)的坐标。这些坐标是障碍物的坐标。如果没有障碍物,输入为(−1, −1)。

第五行是一系列富兰克林的动作,包括 t 个大写字母:分别代表北、东、南、西、停车和保持的N、E、S、W、P和K。

8.7 输出格式


8.8 测试


示例输入 1:

3 1 8 
(-1, -1) 

示例输出 1:



示例输入 2:

3 3 4

示例输出 2:



示例输入 3:

3 3 10 

示例输出 3:


8.8 数据约束


对于第1和第2个测试案例,即1.in和2.inopen in new window

  • 游戏地图是单行的,即车辆不能垂直移动。
  • 您可以简单地忽略所有要求您向N/S移动的指令。
  • 注意,汽车仍然可以面朝北方或南方。这可能会影响它的速度。

对于第1-4个测试案例,即1.inopen in new window, 2.inopen in new window, 3.in和4.inopen in new window

  • 没有给出障碍物;
  • 您可以假设车辆不会撞到障碍物;
  • 但是,如果车辆撞到墙壁,要小心处理!

对于另外20%的数据,即5.in和6.inopen in new window

  • 它们是边界案例;
  • 如果您在这两个测试案例上得到错误答案,请仔细检查您的代码,看看它在特殊情况下是否正确工作。

对于所有测试案例,1n1 \leq nm64m \leq 641t321 \leq t \leq 32;设oo12(m+n)\frac{1}{2}(m + n),则1kologo1 \leq k \leq o \log o


  • 在编写任何代码之前,请确保您已经理解了上面的每一句话!
  • 请注意原点坐标是(0, 0)。
  • 请注意道路上有一些由警方设置的障碍物。当富兰克林遇到这些障碍时,他不能驶过它们。
  • 请注意富兰克林不能越过地图边界。
  • 您不需要弄清楚为什么k的约束是这样的。


AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQopen in new window


贡献者: AndersonHJB
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 按正序
  • 按倒序
  • 按热度