Tilt The Board

題目敘述

You probably have heard of "2D tilt maze" before. It is created by Andrea Gilbert, a software engineer living in England. Ever since its first Internet appearance in 1998, 2D tilt maze has always been one of the most popular online puzzles in the world. However, in this problem, we play a new version of 2D tilt maze.

In the new version of 2D tilt maze, there are $N$ red balls sit in a $S \times S$ sized flat board containing $M$ blue squares and $K$ holes. There will be $Q$ instructions, each of them tilts the board once, and the balls start rolling. A ball rolls in a straight line until it hits a wall, falls into a hole or hits another ball (when a ball stops, it is like a obstacle). The next instruction can only be executed after all the balls stop moving.

When a ball encounters a blue square, you score one point, and the blue square disappears immediately. When a ball falls into a hole, it will fill up the hole and the hole becomes plain ground, no more balls can fall into that hole again, hence the total number of balls will decrease by one.

Now, it is your task to calculate, how many point can you score after executing all the instructions?

The figure below is an example of maze with only one ball, one blue square and no holes. It can be looked upon as a $5 \times 5$ grid with some lines omitted. The position ($x$,$y$) of the corner cell is (1,1)(north-west corner), (1,5)(north-east corner), (5,1)(south-west corner), (5,5)(south-east corner). The line pattern of every cell of this grid can then be represented by a hexadecimal number, so the maze below can be represented as:

輸入說明

The first line of the input contains an integer $T$ ($1 \leq T \leq 100$), the number of test cases. Each test case is formatted as follows.

$S\;N\;M\;K\;Q$

$m_{11}\;m_{12}\;\cdots\;m_{1S}$

$m_{21}\;m_{22}\;\cdots\;m_{2S}$

$\vdots$

$m_{S1}\;m_{S2}\;\cdots\;m_{SS}$

$Bx_{1}\;By_{1}$

$Bx_{2}\;By_{2}$

$\vdots$

$Bx_{N}\;By_{N}$

$Sx_{1}\;Sy_{1}$

$Sx_{2}\;Sy_{2}$

$\vdots$

$Sx_{M}\;Sy_{M}$

$Hx_{1}\;Hy_{1}$

$Hx_{2}\;Hy_{2}$

$\vdots$

$Hx_{K}\;Hy_{K}$

$c_{1}\;c_{2}\;\cdots\;c_{Q}$

The first line of each test case consists of 5 integers $S$ ($1 \leq S \leq 10$), $N$, $M$, $K$ ($0 \leq N,M,K \leq S \times S$, $0 \leq N+M+K \leq S \times S$) and $Q$ ($1 \leq Q \leq 30$) representing the size of the board, the number of red balls, the number of blue squares, the number of holes and the number of instructions. Then $S$ lines follow, each containing $S$ hexadecimal numbers representing the line pattern of each cell. It is guaranteed that the board is completely surrounded by walls.

The next $N$ lines, each containing 2 space-separated integers $x$, $y$, represent the starting position of the red balls.

The next $M$ lines, each containing 2 space-separated integers $x$, $y$, represent the position of the blue squares.

The next $K$ lines, each containing 2 space-separated integers $x$, $y$, represent the position of the holes.

All of the $x$, $y$ coordinates in the above $N+M+K$ lines satisfy $1 \leq x,y \leq S$ and there will be no repeating coordinates (i.e. at the beginning, all the red balls, blue squares and the holes are all different).

The next line contains $Q$ characters, each of them are either N, E, S or W, meaning that we are tilting the board at the side of north, east, south or west, respectively. Whenever we tilt the board on one side, the balls rolls to the other side, for example, if we tilt the board on the side of north, the balls will roll form north to south.

輸出說明

For each test case, output an integer, which denotes the points scored after all the tilting instructions, in a line.

範例輸入

範例輸出

1
3
2

提示

Judge Setting

run-time limit: 500 ms
memory limit: 262144 byte
測資數量: 0