ZOAC 3

면접 대비

시간 제한1초메모리 제한1024 MB

요약

두 손가락이 QWERTY 자판의 주어진 키에서 시작하고, 자음은 왼손, 모음은 오른손으로 입력하며 손가락을 옮기는 데 맨해튼 거리만큼 시간이 걸린다. 주어진 문자열을 입력하는 최소 시간을 구한다.

문제

2020년 12월, 세 번째로 열린 ZOAC의 오프닝을 맡은 성우는 누구보다 빠르게 ZOAC를 알리려 한다.

하지만 안타깝게도 성우는 독수리타법이다!

독수리타법이란 양손의 검지손가락만으로 타자를 치는 방식이다.
성우는 한글 자음 쪽 자판은 왼손 검지손가락으로, 한글 모음 쪽 자판은 오른손 검지손가락으로 입력한다.
a의 좌표가 (x1, y1)이고 b의 좌표가 (x2, y2)일 때, a에 있는 성우의 손가락이 b로 이동하는 데 걸리는 시간은 a와 b의 택시 거리 |x1-x2|+|y1-y2|이다.
키를 한 번 누르는 데 1의 시간이 걸린다.
성우는 두 손을 동시에 움직일 수 없다.
성우가 사용하는 키보드는 쿼티식 키보드이며, 아래 그림과 같다.

바쁜 성우를 위해 주어진 문자열을 출력하는 데 걸리는 시간의 최솟값을 구하자.

첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다.

그다음 줄에는 알파벳 소문자로 이루어진 문자열이 주어진다. 문자열의 길이는 최대 100자이다. 빈 문자열은 주어지지 않는다.

입력으로 주어진 문자열을 출력하는 데 걸리는 시간의 최솟값을 출력한다.

성우가 두 손을 동시에 움직이지 못하는 이유는 다음과 같다.