The (Bayesian) Hound and the Hare

Researchers have found that hounds are remarkably intelligent — so intelligent that they hunt their prey using Bayesian statistics.

For an experiment, a blindfolded hound is placed in a maze laid out on a square grid, with a hare somewhere else in the maze. Once every second the hare takes one step of one unit in a random direction (never diagonally), chosen uniformly at random among the directions not blocked by a wall. Sometimes, when the hare steps, it makes a little noise at its new cell. The hound hears this noise with uncertainty $\sigma$: if the hare is at $(x, y)$, the hound believes it heard the hare at $(x', y')$ with probability

$N \exp\!\left(-\frac{(x - x')^2 + (y - y')^2}{2\sigma^2}\right)$

where $N$ is the appropriate normalization factor.

The hound keeps a belief — a probability distribution over the hare's cell — and reasons about it as follows. Before the first observation the belief is uniform over every open cell. Then, for each observation, in order:

1. Hare step. Each cell's probability is spread equally over its open neighbors (the same random walk the hare performs).
2. Update. If the hound heard a noise at $(x', y')$, every cell $(x, y)$ is reweighted by $\exp\!\left(-\frac{(x - x')^2 + (y - y')^2}{2\sigma^2}\right)$ and the belief is renormalized. A silence line carries no information about position and leaves the belief unchanged.
3. Move. The hound then considers staying put and each legal one-cell move, and picks the one that minimizes the expected shortest-path distance to the hare under the current belief (the maze is traversed only in the four cardinal directions, never through walls or diagonally).

When two candidate moves give expected distances within $10^{-5}$ of each other they are treated as tied, and the hound prefers, in order: staying still, then North, then East, then South, then West.

Neither the hound nor the hare may enter a wall or move diagonally, and the hound knows this. The hound has perfect memory and knows the maze exactly. It also assumes it might share a cell with the hare without realizing it.

Determine the path the hound takes for the given sequence of observations.

The maze is $X$ units wide (West to East) and $Y$ units tall (North to South).

• The first line contains two integers $X$ and $Y$ ($3 \le X, Y \le 100$).
• The next $Y$ lines give the maze, one row each. The first row is the northernmost strip and, within a row, the first character is the westernmost cell. # is a wall, . is open space, and h marks the hound's starting cell. The outer border is always wall, and the open interior is connected.
• The next line contains the integer $\sigma$ ($\sigma \ge 1$).
• Each remaining line is one observation, one per second. A line reading silence means the hound heard nothing. Otherwise the line holds two integers — the column and the row (with the northwest corner at $(0, 0)$) where the hound believes it heard the hare. These coordinates may lie outside the maze.

For each observation, print on its own line one of N, S, E, W, or . — meaning that after processing that observation the hound moves North, South, East, West, or stays in place, respectively.