과학자
시간 제한2초메모리 제한128 MB
격자 미로 안에서 보이지 않는 쥐가 상자 가장자리를 밀어 발생시킨 상자 이동 기록이 주어질 때, 이를 만족하는 쥐의 최소 이동 횟수를 구합니다.
문제
한 과학자가 실험용 쥐를 N×N개의 정사각형 칸으로 이루어진 우리에 넣었다. 각 칸은 흰색이거나 빨간색이다. 행은 위에서 아래로 1번부터 N번까지, 열은 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있다.
쥐는 왼쪽, 오른쪽, 위, 아래의 네 방향으로 한 칸씩 이동할 수 있다. 빨간색 칸을 무서워하므로 빨간 칸에는 절대 들어가지 않는다.
이제 쥐는 K×K 크기의 상자 안에 있다. 상자의 변은 우리 격자의 변과 평행하다. 상자 안은 매우 어둡지만, 쥐는 어떤 칸이 빨간 칸인지 정확히 알고 있어서 빨간 칸으로 이동하지 않는다.
과학자는 상자 안의 쥐 위치를 볼 수 없고, 밖에서 상자의 움직임만 볼 수 있다. 쥐가 상자의 가장자리에서 바깥쪽으로 한 칸 이동하려고 하면, 상자는 그 방향으로 한 칸 움직이고 쥐도 상자와 함께 그 방향으로 한 칸 이동한다.
그림에서 검은 원은 쥐를, 회색 직사각형은 상자를 나타낸다.
상자의 처음 위치와 이후 상자가 움직인 방향들이 주어질 때, 그 움직임들을 만들기 위해 쥐가 최소 몇 번 이동해야 하는지 구하라.
입력
첫째 줄에 우리의 크기 N과 상자의 크기 K가 주어진다. (2 ≤ K ≤ 10, K < N ≤ 100)
다음 N개 줄에는 우리의 각 칸이 빨간 칸(r)인지 흰 칸(w)인지 주어진다.
다음 줄에는 상자의 처음 위치 R과 C가 주어진다. 이 좌표는 상자의 왼쪽 위 꼭짓점이다. (1 ≤ R, C ≤ N-K+1)
다음 줄에는 상자가 움직인 횟수 M이 주어진다. (1 ≤ M ≤ 100,000)
마지막 줄에는 상자가 움직인 방향이 순서대로 주어진다. 각 문자는 L, R, U, D 중 하나이다.
출력
입력으로 주어진 방향대로 상자를 움직이게 하려면 쥐가 최소 몇 번 이동해야 하는지 첫째 줄에 출력한다.