시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 87 32 20 35.714%

문제

그림 1의 왼쪽은 4x7 크기의 가상 키보드를 보여주며, 사용자가 텍스트를 입력하기 위해서는 가상 키보드의 키를 직접 누르는 대신에 그림 오른쪽에 보여지는 5개의 하드웨어 버튼을 이용해야 합니다. 가상 키보드의 왼쪽 맨 위 키의 위치에서 시작하는 “커서”가 있으며, 네 개의 화살표 버튼은 커서의 움직임을 제어합니다. 화살표를 한 번 누르면 다른 글자가 나올 때까지 그 방향으로 이동하지만, 그런 글자가 없으면 이동하지 않습니다. 커서가 적절한 키 위에있을 때 선택 (SEL) 버튼을 누르면 해당 문자가 선택되고 텍스트의 끝에 추가됩니다. 이러한 방식으로 주어진 텍스트의 문자들을 입력할 수 있으며 텍스트를 종료하려면 사용자가 Enter 키를 찾아 선택해야 (즉, 선택 버튼을 눌러야) 합니다.

그림 1. 가상키보드와 하드웨어 버튼의 예시

그림 1은 주어진 가상 키보드에서 CONTEST라는 텍스트를 입력하는 방법을 보여줍니다. 화살표는 화살표 버튼이 눌러지는 과정에서 커서가 이동한 모습을 보여주며, 점은 선택 버튼을 누를 가상 키를 나타냅니다. 더불어 CONTEST를 입력하기 위해 30번의 키 입력이 있었다는 것을 확인할 수 있습니다.

이 문제에서는 가상 키보드 레이아웃이 제공되며 텍스트가 주어집니다. 이 때, 텍스트를 입력하는데 필요한 최소 키 입력의 개수를 찾아야 합니다.

입력

입력의 첫 번째 줄(행)에는 두 개의 정수 r과 c (1 ≤ r, c ≤ 50)가 포함되어 가상 키보드 격자의 행과 열 수를 제공합니다. 가상 키보드는 다음 r 행에 표시되며 각 행에는 c 문자가 들어 있습니다. 이러한 문자의 가능한 값은 대문자, 숫자, 대시 및 별표 (Enter를 나타냄)입니다. 주어진 문자에 해당하는 키는 하나뿐입니다. 각 키는 하나 이상의 격자 사각형으로 구성되며, 항상 연결된 영역을 형성합니다. 입력의 마지막 행에는 입력 할 텍스트가 들어 있습니다. 이 텍스트는 10,000개 이하의 문자로 구성된 문자열이며, 별표 문자는 포함되지 않고, 빈 문자열이 주어지지 않습니다. 주어진 텍스트는 주어진 가상 키보드로 입력될 수 있습니다.

출력

마지막에 Enter 키를 포함하여 전체 텍스트를 입력하는 데 필요한 최소 키 입력 수를 출력합니다.

예제 입력 1

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

예제 출력 1

30

예제 입력 2

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

예제 출력 2

160

예제 입력 3

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

예제 출력 3

19

예제 입력 4

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

예제 출력 4

7

출처

ACM-ICPC > World Finals > 2015 World Finals F번

  • 잘못된 번역을 찾은 사람: jh05013