Researchers have discovered that hounds are extremely intelligent -- so intelligent, in fact, that they use Bayesian statistics to hunt down their prey.
As an experiment, researchers studying these hounds blindfold one and put it in a maze laid out on a square grid. They put a hare somewhere else in the maze. Once every second, the hare takes a step one unit in a random direction (no diagonals), chosen uniformly at random among the directions that aren't blocked by walls. Sometimes, when the hare takes a step, it makes a little bit of noise at its new position. The hound hears the noise with a certain amount of uncertainty s -- that is, if the hare is at position (x,y), then the hound thinks that it heard the hare at position (x',y') with probability N*exp(-((x-x')*(x-x')+(y-y')*(y-y'))/(2s*s)) where N is an appropriate normalization factor.
After every step the hare takes, the hound moves one unit in the direction (North, East, South, or West, or not moving at all) that minimizes the expected shortest-path distance to the hare. In case of a tie, the hound favors not moving, than North, than East, than South, than West. If the difference between the expected distances of two choices is within 10-5, the hound will choose according to its favor. (That is, the hound first considers whether to go West; if the expected distance after going South is lower or within 10-5, the hound considers going South instead; then, if going East is better or within 10-5, the hound considers going East; then North; then staying still.)
Neither the hound nor the hare can walk into a wall or on a diagonal, and the hound knows this. The hound has a perfect memory and knows the exact layout of the maze. The hound assumes that the hare starts at a uniform random location within the maze, and that it could occupy the same space as the hare without realizing it.
Write a program that determines what path the hound takes given a sequence of observations.
The first line of the input file contains an integer indicating the number of test cases.
For each test case, the first line is two integers, X and Y. The maze has dimension X units (West to East) by Y units (North to South). You may assume that 3<= X,Y<=100. This is followed by a map of the maze. The first line corresponds to the northernmost strip of the maze, and the first column is the western side. A "#" indicates a wall, a "." indicates open space, and a "h" marks the starting position of the hound. The sides of the maze are always walls, and the interior of the maze is connected.
The map of the maze is followed by an integer, 1<=s<=50, on one line. The next line is the number of observations Q<=2000 (one per second), and each of the next Q lines describe an observation. A line that contains "silence" indicates that the hound hears nothing, and a line that contains two integers gives the coordinates -- column, row in which the hound thinks it heard the hare. The northwest corner of the maze is (0,0). Note that the coordinates may be outside the maze.
For each observation, output "N", "S", "E", "W", or "."
if the hound goes North, South, East, West, or stays still, respectively, after each observation.
1 20 20 #################### #################### ####.....h.....##### ####.#########.##### ####.#########.##### ####.#########.##### ####.#########.##### ####.#########.##### ####...........##### ####.#########.##### ####.#########.##### ####.#########.##### ####...........##### #########.########## #########.########## #########.########## #########.########## #################### #################### #################### 5 6 silence silence silence 10 8 9 8 8 9
E E E E E S
Migrated from old NTUJ.
MIT Team 2008
| No. | Testdata Range | Score |
|---|