(베이지안) 사냥개와 토끼

연구자들은 사냥개가 매우 영리하다는 사실을 밝혀냈다. 얼마나 영리한지, 사냥개는 베이즈 통계를 이용해 먹이를 추적한다.

한 실험에서, 눈을 가린 사냥개를 정사각형 격자로 이루어진 미로에 넣고 토끼를 미로의 다른 곳에 둔다. 토끼는 매 초마다 한 칸씩(대각선 제외) 이동하는데, 벽으로 막히지 않은 방향들 중 하나를 균등한 확률로 골라 움직인다. 토끼가 이동할 때 가끔 새로 도착한 칸에서 작은 소리를 낸다. 사냥개는 이 소리를 불확실성 $\sigma$ 를 가지고 듣는다. 즉, 토끼가 $(x, y)$ 에 있을 때 사냥개가 소리를 $(x', y')$ 에서 들었다고 생각할 확률은

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

이고, 여기서 $N$ 은 적절한 정규화 상수이다.

사냥개는 토끼의 위치에 대한 확률 분포(믿음)를 유지하며 다음과 같이 갱신한다. 첫 관측 이전의 믿음은 모든 열린 칸에 대해 균등하다. 이후 각 관측마다 다음을 순서대로 수행한다.

1. 토끼의 이동. 각 칸의 확률을 그 칸의 열린 이웃들에 균등하게 나누어 분배한다(토끼가 실제로 하는 무작위 이동과 같다).
2. 갱신. 사냥개가 $(x', y')$ 에서 소리를 들었다면, 모든 칸 $(x, y)$ 의 확률에 $\exp\!\left(-\frac{(x - x')^2 + (y - y')^2}{2\sigma^2}\right)$ 를 곱한 뒤 믿음을 다시 정규화한다. silence 줄은 위치에 대한 정보를 주지 않으므로 믿음을 바꾸지 않는다.
3. 이동. 그런 다음 사냥개는 제자리에 머무는 것과 인접한 한 칸으로 가는 각 합법적인 이동을 고려하여, 현재 믿음 하에서 토끼까지의 기대 최단 경로 거리를 최소화하는 선택을 한다(미로는 네 방향으로만 이동할 수 있고 벽이나 대각선으로는 지날 수 없다).

두 후보 이동의 기대 거리가 $10^{-5}$ 이내로 차이 나면 동점으로 간주하며, 이때 사냥개는 제자리, 북, 동, 남, 서의 순서로 선호한다.

사냥개도 토끼도 벽에 들어가거나 대각선으로 움직일 수 없으며, 사냥개는 이 사실을 알고 있다. 사냥개는 완벽한 기억력을 가지고 있고 미로의 구조를 정확히 알고 있다. 또한 사냥개는 자신이 토끼와 같은 칸에 있으면서도 이를 알아채지 못할 수 있다고 가정한다.

주어진 관측 순서에 대해 사냥개가 이동하는 경로를 구하는 프로그램을 작성하라.

미로의 크기는 서쪽에서 동쪽으로 $X$ 칸, 북쪽에서 남쪽으로 $Y$ 칸이다.

• 첫째 줄에 두 정수 $X$ 와 $Y$ 가 주어진다 ($3 \le X, Y \le 100$).
• 다음 $Y$ 개의 줄에 미로가 한 줄에 한 행씩 주어진다. 첫 번째 줄이 가장 북쪽 줄이고, 한 줄에서 첫 번째 문자가 가장 서쪽 칸이다. # 는 벽, . 는 열린 공간, h 는 사냥개의 시작 칸을 나타낸다. 미로의 바깥 경계는 항상 벽이며, 열린 내부는 연결되어 있다.
• 다음 줄에 정수 $\sigma$ 가 주어진다 ($\sigma \ge 1$).
• 나머지 각 줄은 매 초의 관측 하나를 나타낸다. silence 라고 적힌 줄은 사냥개가 아무 소리도 듣지 못했음을 뜻한다. 그렇지 않으면 그 줄에는 두 정수, 즉 사냥개가 토끼의 소리를 들었다고 생각하는 위치의 열과 행이 주어진다(북서쪽 모서리가 $(0, 0)$). 이 좌표는 미로 밖일 수도 있다.

각 관측에 대해, 사냥개가 그 관측을 처리한 뒤 북/남/동/서로 이동하는지 아니면 제자리에 머무는지에 따라 N, S, E, W, . 중 하나를 한 줄에 하나씩 출력한다.