문제

현대모비스는 운전자가 안전하게 편리하게 주행하도록 도와주는 ADAS 시스템을 개발했다. ADAS 시스템의 개발 담당 사원 구름이는 ADAS 시스템을 보완하기 위해서 가상 주행을 진행하고, ADAS시스템이 이동한 경로의 위험 점수를 측정하려고 한다.

가상 주행 환경은 차원 좌표 평면으로 표현할 수 있다. 좌표 평면은 위 아래로 줄, 좌우로 줄의 격자로 구성되어 있으며, 맨 왼쪽 위 좌표는 , 맨 오른쪽 아래 좌표는 이다. 이 때 임의의 정수 에 대해 좌표의 점은 일반 점 혹은 -점, 혹은 점 , 점 중 하나로 표현된다.

가상 주행 시스템은 점 에서 시작해서 점 으로 이동하며, 점 에 도착하는 순간 주행이 종료된다. 주행 과정에서 ADAS 시스템은 다음 조건에 따라 이동한다.

• 주행 과정에서 어떤 점 에 방문하면, ADAS 시스템은 의 해당 점 주변 방향의 점 중, 아직 방문한 적 없는 점들을 이동 후보 정점 목록에 추가한다. 좌표 평면 바깥에 해당하는 점인 경우는 후보에서 제외한다.
• ADAS 시스템은 이동 후보 정점 목록 중에서 방문할 다음 점을 아래의 우선순위에 따라 결정한다.
• 점 가 가장 우선순위가 높으며, 다음은 -점, 그 다음은 일반점이다. 우선순위가 가장 높은 점을 먼저 방문한다.
• 우선순위가 같은 점이 여러 개 있다면, 점의 좌표를 로 표현했을 때 값이 작은 것이 우선, 값이 같다면 값이 작은 것을 우선적으로 방문한다.

가상 주행 과정에서 위험 점수는 처음에 점에서 시작하며, 각 점을 방문할 때 다음 규칙에 따라 위험 점수가 증가한다.

• 점 와 점 는 방문할 때 위험 점수가 증가하지 않는다.
• 일반 점의 경우, 해당 점을 중심으로 주변 크기 안에서 자신을 제외한 -점의 개수만큼 위험 점수가 증가한다. 따라서, 아래 그림의 일반점은 위험 점수가 점이 된다.

• -점의 경우, (일반 점과 동일한 방식으로 계산한 위험 점수 - ) 만큼 위험 점수가 증가한다. 이 값이 음수인 경우 위험 점수가 그만큼 감소한다.

모든 주행을 마친 후, 위험 점수가 보다 작다면 위험 점수는 으로 측정한다.

ADAS 시스템은 목적지에 도착하면 가상 주행을 종료한다. 이때 ADAS 시스템이 측정한 위험 점수를 출력해보자.

예시

현재 ADAS 시스템의 정보 수집으로 얻은 도로의 좌표평면이 아래와 같다고 하자.

• 점 가 좌표 에 있으므로 주행은 에서 시작한다. 이 때 위험 점수는 점이다.

• 다음으로, 이동할 후보 정점에 세 개의 정점이 추가된다. 그림에서 방문한 정점은 노란색, 후보 정점은 초록색으로 나타나있다. 세 정점 모두 일반 정점이므로 우선순위는 동일하고, 우선 순위가 같은 정점이 여러 개인 경우 다음 정점을 선택하는 규칙에 따라 ADAS 시스템은 정점에 방문하게 된다.

• 정점은 규칙에 따라 위험 점수가 점이므로, 위험 점수가 만큼 상승한다. 다음으로, 이동할 후보 정점에 두 개의 점이 추가된다. 총 개의 후보 정점 중에서, 가장 우선순위가 높은 건 -점인 과 의 두 개 정점이다. 마찬가지로, 우선 순위가 같은 정점이 여러 개인 경우 다음 정점을 선택하는 규칙에 따라 ADAS 시스템은 정점에 방문하게 된다.

• 정점은 규칙에 따라 위험 점수가 점이 되므로, 위험 점수가 만큼 감소한다. 다음으로, 이동할 후보 정점에 두 개의 점이 추가된다. 이 중에서 가장 우선순위가 높은 점은 점 인 이므로, 에 방문한다.
• 점 에 방문했으므로, 주행을 종료한다. 이 가상주행의 위험 점수는 이므로 을 출력한다.

입력

첫째 줄에 좌표 평면의 크기 가 공백을 두고 주어진다. 둘째 줄부터 개의 줄에 걸쳐 각 점의 종류가 무엇인지, 길이가 인 문자열로 주어진다. 둘째 줄부터 번째로 주어지는 줄의 번째 문자는 좌표에 해당하는 점이 어떤 종류의 점인지를 나타낸다. 입력으로 주어지는 문자열은 의 종류의 문자로만 구성되며, 각각 해당 점이 점 , 점 , -점, 일반 점 임을 나타낸다. 입력에서 시작점과 도착점을 나타내는 문자 와 는 정확히 하나씩 주어진다.

• 
• 와 는 정수이다.

출력

첫째 줄에 문제에서 제시된 조건에 따라 ADAS 시스템이 가상 주행을 수행한 후 측정한 위험 점수를 출력한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!