AncientGameRecord

This task is about an ancient game. The game is played on a rectangular board divided into a grid of n rows by m columns of cells. You are given the ints n and m. Rows are numbered 0 through n-1 from top to bottom, columns are numbered 0 through m-1 from left to right. We will use (x, y) to denote a cell in row x and column y.

At any point during the game each cell is either empty or it contains exactly one token. A move in the game looks as follows: The player selects a cell and a direction: up, down, left, or right. The selected cell must contain a token. There must be a next cell in the chosen direction, and that cell must be empty. The actual move then consists of taking the token and moving it into the next cell in the chosen direction.

You are given a list of moves: two int[]s x and y and a String d. For each valid i, the values x[i], y[i] and the character d[i] describe one move in which the player selects the cell (x[i], y[i]) and the direction d[i]. Each direction will be one of 'U', 'D', 'L', 'R', standing for up, down, left, and right, respectively. Note that 'U' represents the move from (x, y) to (x-1, y), and 'L' represents the move from (x, y) to (x, y-1).

A list of moves is called valid if there is some initial configuration of arbitrarily many tokens on the board (with at most one token in each cell) such that it is possible to perform all the moves on the list in the given order. I.e., when executing the moves one after another, the chosen cell must always contain a token and the chosen direction must always point to an empty adjacent cell.

We want to change the given list of moves into a valid list. We can erase some moves from the given list, without changing the relative order of the other moves on the list. Compute and return the smallest number of moves we have to erase.