정원 방어

흔히 “필요는 발명의 어머니”라고 하지만, 어떤 사람에게는 “게으름”이 발명의 부모에 더 가깝다.

허버트 그린섬(Hubert Greenthumb)은 울타리 기둥 박는 일을 몹시 싫어했다. 하지만 정원에 울타리가 없으면 근처 숲에서 온 사슴이 수확도 하기 전에 채소를 다 먹어 치운다는 것을 알고 있었다.

손재주가 있던 그는 작은 정원용 트랙터, 한물간 컴퓨터 칩 몇 개, 로봇 팔 두 개로 자동 울타리 설치 기계를 만들었다. 원하는 울타리 모양을 입력하면 기계가 마당을 돌아다니며 1피트 단위로 울타리를 놓아 작업을 끝낸다.

허버트는 100피트 × 100피트 마당 안에 한 변이 25피트인 정사각형을 두르도록 입력한 뒤 기계를 켜고 안으로 들어갔다. 다시 나와 보니 기계는 복잡하고 무작위처럼 보이는 경로를 따라 울타리를 놓아 두었다. 그는 무언가 잘못됐다고 인정하는 대신, 기계가 실제로 둘러싼 영역을 그대로 정원으로 쓰기로 했다. 사슴이 더 이상 들어갈 수 없는(울타리로 완전히 둘러싸인) 마당의 모든 부분이 정원이 된다.

씨앗을 알맞게 사려면 둘러싸인 넓이를 알아야 한다. 로봇의 시작 위치와 이동 순서가 주어질 때, 둘러싸인 넓이가 몇 제곱피트인지 구하여라.

마당은 1피트짜리 칸으로 이루어진 100 × 100 격자다. 로봇은 격자의 변을 따라 이동하며 격자의 꼭짓점에서 꼭짓점으로 울타리를 놓는다. 울타리는 격자 변 위에 정확히 놓이므로 넓이를 차지하지 않는다. 예를 들어 로봇이 북쪽으로 1, 동쪽으로 1, 남쪽으로 1, 서쪽으로 1 이동하면 정확히 1제곱피트를 둘러싼다.

첫째 줄에 데이터 집합의 개수가 주어진다. 데이터 집합 사이에는 빈 줄이 없다.

각 데이터 집합의 첫째 줄에는 정수 세 개 X Y Z가 주어진다. (X, Y)는 격자에서의 시작 위치이고, Z는 이동 횟수다. X는 마당 서쪽 끝에서부터의 거리(피트), Y는 남쪽 끝에서부터의 거리(피트)이며, 둘 다 0 이상 100 이하다.

다음 Z개의 줄에는 각각 방향 문자 D(N, S, E, W 중 하나)와 정수 F가 공백으로 구분되어 주어진다. 이는 로봇이 방향 D로 F피트 이동함을 뜻한다.

경로는 절대 100 × 100 마당을 벗어나지 않는다. 경로는 닫혀 있을 수도, 아닐 수도 있다. 스스로 교차하거나 이미 울타리를 놓은 변을 다시 지날 수도 있다(다시 지나도 새 울타리는 놓이지 않는다).

각 데이터 집합마다 다음 형식으로 한 줄을 출력한다.

Data Set N: Q square feet.

여기서 N은 1부터 시작하는 데이터 집합 번호이고, Q는 울타리로 둘러싸인 넓이(제곱피트)다. 마지막 데이터 집합의 출력 뒤에는 End of Output을 한 줄에 출력한다.