409969: GYM103870 N Schemy

Codicon is traversing through an $$$N$$$x$$$N$$$ grid ($$$2 \leq N \leq 1000$$$). He starts at the top left cell and goes to the bottom right, where in each step he either moves one block down or one block right. Chessbot however, has a scheme and would like Codicon to traverse a specific path (for no nefarious reason of course). He will do this by strategically placing impassable rocks in certain spots (not at the start or end cell). But rocks cost a lot of money, so being the thrifty person he is Chessbot would like to use as little rocks as possible to make his path the only valid path Codicon can take. Find the minimum amount of rocks needed to do so.

A valid path is one where Codicon starts in the top left, ends in the bottom right, only moves right or down, and does not pass any rocks.

The first line has one integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) denoting the number of tests.

Each of $$$T$$$ tests has two lines. The first line contains only the integer $$$N$$$. The second line has a string of length $$$2 \cdot N - 2$$$ denoting the path Chessbot wants Codicon to take in the form of 'R's and 'D's, where 'R' signals he wants Codicon to go one block to the right and 'D' signals he wants Codicon to go one block down. The sum of $$$N^2$$$ across all tests is guaranteed to be less than or equal to $$$10^6$$$.

For each test case, a single integer denoting the minimum number of rocks needed to make the path Chessbot wants to be the only valid path.

2
6
RRDDRRRDDD
5
DDDRDRRR

7
5

For this explanation we'll use cartesian coordinates where the top left cell is $$$(1, 6)$$$. For the first case, note that if Chessbot places rocks in the cells $$$(1, 5)$$$, $$$(2, 5)$$$, $$$(3, 3)$$$, $$$(4, 2)$$$, $$$(4, 5)$$$, $$$(5, 3)$$$, $$$(5, 6)$$$ then Codicon must take the desired path. It can be proven that this is the least amount of rocks necessary to do so.

$$$-------------------------------------------------$$$

Idea: Bossologist

Preparation: Bossologist

Occurrences: Intermediate 12, Advanced 9