2132. The Wall That Refuses a Move
A robot stands at row 0, column 0 of an r by c grid. Some cells hold a
wall. The robot reads a string of commands:
U row - 1 D row + 1
L column - 1 R column + 1
A command is carried out only if the cell it would move into is inside the grid and does not hold a wall. Otherwise the robot STAYS WHERE IT IS and the command is counted as refused. Either way the command is consumed: the robot never retries it.
Print the final row, the final column, and how many commands were refused.
``` r = 3, c = 3, no walls, "RRDD" -> 2 2 0 r = 3, c = 3, wall at (0,1), "RRDD" -> 2 0 2
the first R is refused by the wall, the second R is refused by the same wall, then DD walks down column 0 ```
## What most people try first
Move first and repair afterwards: step the robot, then if it has landed outside the grid or on a wall, step it back. That gets the position right and the COUNT wrong, because a command that was repaired is indistinguishable afterwards from one that was never attempted, and the natural place to increment the counter is reached in both cases. Test the robot's intended destination BEFORE moving it, and the two outcomes stay separate.
## The rule is one test with three parts
nr, nc = the cell the command points at
if nr, nc is inside the grid and is not a wall:
the robot moves there
else:
refused = refused + 1 and the robot does not move
The bounds test must come before the wall test, in the same expression and in that order. Checking the wall first means reading a cell that may be outside the grid, which crashes in C and C++ and, in a flat array, silently reads the wrong row.
## Why a refused command is not the same as a wasted one
A robot that stands still still consumes the command. So two R commands against
the same wall count as two refusals, not one, and the robot does not creep past
the wall on the second attempt. The declared test with a wall at (0,1) and
the commands RRDD is exactly this case.
## Cost
O(r c) to mark the walls, then O(1) per command, so O(r c + m) in total
where m is the number of commands. Holding the walls in a grid of booleans
costs O(r c) memory and makes each test one array read.
Constraints - `1 ≤ r, c ≤ 1000` - `0 ≤ k ≤ 1000` - `1 ≤ length of the command string ≤ 50000` - cell `(0, 0)` never holds a wall - no wall is listed twice - a refused command is still consumed and is never retried
Input
The first line contains three integers r, c and k: the number of rows, the number of columns, and the number of walls.
Each of the next k lines contains two integers, the row and the column of one wall.
The last line contains the command string, each character one of U, D, L or R.
Output
Print one line holding three integers separated by single spaces: the final row, the final column, and the number of refused commands.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.