Minimum Rejections for Safe Robot Movement

A robot receives a sequence of \(N\) commands but it does not want to step on obstacles or leave the grid boundary. In order to ensure safety, the robot may choose to reject some commands. Your task is to compute the minimum number of rejected commands such that the robot, when executing the remaining commands in order, never moves into an obstacle or out of the grid.

The robot understands the following commands:

• FORWARD: move one unit in the current direction.
• BACK: move one unit in the opposite direction.
• LEFT: rotate left by \(90^\circ\) (without changing position).
• RIGHT: rotate right by \(90^\circ\) (without changing position).

Initially, the robot is facing upward (direction \(0\) corresponding to up). The grid is represented as a rectangle of size \(R \times C\) with rows numbered from 0 to \(R-1\) and columns from 0 to \(C-1\). There are obstacles placed in some cells. The robot starts at a given cell \((r_0, c_0)\). A move is considered illegal if the robot attempts to move into an obstacle cell or outside the grid boundaries.

You are allowed to reject any command. The accepted commands are executed sequentially. Your goal is to minimize the number of rejected commands (equivalently, maximize the number of accepted commands) such that every move command that is executed keeps the robot in a safe cell.

Note: Decisions are made in order; that is, when processing the \(i\)th command, you can choose to either execute it (if it leads to a legal state) or reject it, and then proceed to the next command.

The moves are defined as follows. Let the current direction be \(d\) with the following mapping: \(0\): up, \(1\): right, \(2\): down, \(3\): left. Then:

• FORWARD: If \(d=0\), move from \((r, c)\) to \((r-1, c)\); if \(d=1\), to \((r, c+1)\); if \(d=2\), to \((r+1, c)\); if \(d=3\), to \((r, c-1)\).
• BACK: Move in the opposite direction: if \(d=0\), from \((r, c)\) to \((r+1, c)\); if \(d=1\), to \((r, c-1)\); if \(d=2\), to \((r-1, c)\); if \(d=3\), to \((r, c+1)\).
• LEFT: Change direction to \((d+3) \bmod 4\).
• RIGHT: Change direction to \((d+1) \bmod 4\).

Output the minimum number of commands that must be rejected so that the robot never makes an illegal move.

inputFormat

The input is given as follows:

R C
r0 c0
K
r1 c1
r2 c2
... (K lines of obstacle coordinates)
N
command_1
command_2
... (N lines, each is one of FORWARD, BACK, LEFT, RIGHT)

where

• \(R\) and \(C\) are the numbers of rows and columns of the grid.
• \((r0, c0)\) is the starting cell of the robot.
• \(K\) is the number of obstacles, followed by \(K\) lines with the coordinates of each obstacle cell.
• \(N\) is the number of commands to process.

You can assume that the starting cell is not an obstacle and that all obstacle positions lie within the grid.

outputFormat

Output a single integer: the minimum number of commands that must be rejected so that the robot executes only legal moves.

sample

3 3
1 1
0
5
FORWARD
LEFT
FORWARD
RIGHT
FORWARD

1