13454번 - Robert Floyd 다국어

Robert W Floyd was an American computer scientist who was also awarded the Turing Award. In the ACM-ICPC community, his most known work is probably the Floyd-Warshall algorithm which can find all-pairs shortest paths and transitive closure efficiently. It has many applications and many of them is very useful, but the following is not one of them.

Stitches is the terror of Darkshire. He emits a putrid bile along his path that is stinky, disgusting and slows you by 35% percent when walking in it. So in short, you don’t want to stand in them. With Stitches’s movement, he can potentially cut the map into several separated areas. Two areas are separated if there is no way one can reach the other without crossing Stitches’s bile. Stitches always walks along a single direction (up, down, left or right) for a unit of length and then decides whether to change his direction or not. In order to bring peace to Darkshire, the heroes will kill him as soon as possible. You may assume that Stitches only emits bile for at most 2048 units of length, since the heroes will not allow him to walk more.

Unfortunately, Stitches’ bile does not disappear after his death. As the mayor of Darkshire, you want to determine how many separated areas there are after Stitches walks through. So how can we solve this with the Floyd-Marshall algorithm and why is it not useful? Well, because of how Stitches move, we can imagine he is walking on the edges of a square grid of 4098 × 4098 cells. Stitches begins his walk at the center of the grid, thus he will never touch its boundary. Thus easily transform the map into a graph where neighboring blocks on the grid are connected if Stitches did not walk on its connecting edge. After running the Floyd-Marshall algorithm, we can easily determine whether two blocks are in the same area. Then, just simply counting the number of areas by using a data structure for storing disjoint sets. However, since Darkshire is not a small town and there can be more than 16 millions of blocks on the grid, this method will simply not be fast enough. Unless you have the help of bronze dragon Chromie, the Keeper of Time. Please find a better way to solve this problem. Again, cheating with the bronze dragon is not allowed.

On the first line there is a single integer T (T ≤ 30) indicating the number of test cases. For every test case, the sequence of Stitches’ movement will be given on a line with ‘U’ as up, ‘D’ as down, ‘L’ as left and ‘R’ as right. The length of the sequence will not exceed 2048.

Output the number of separated areas on one line.