이미지 인식

아이린은 Novel Efforts in Effective Recognition of Characters(NEERC)에서 일한다. 그녀의 새 프로젝트는 로봇을 이용한 이미지 인식이다.

먼저 아주 단순한 모형에서 시작한다. 고정된 이미지가 $d$개 있으며, 각각 숫자 $0$부터 $d - 1$까지로 불린다. 각 이미지는 흰색과 검은색 단위 정사각형(픽셀)으로 채워진 $w \times h$ 직사각형이다. 모든 이미지는 서로 다르다(어떤 두 이미지도 최소한 한 픽셀에서 다르다).

로봇은 이미지들 중 하나의 왼쪽 위 픽셀에 놓인 뒤, 아래에서 설명하는 언어로 작성된 프로그램을 실행한다. 로봇의 임무는 자신이 어느 이미지 위에 놓였는지 알아내는 것이다.

로봇의 프로그래밍 언어는 다음 명령들로 이루어진다.

• U, D, L, R --- 이동 명령. 로봇을 각각 위, 아래, 왼쪽, 오른쪽으로 한 픽셀 옮긴다. 이동으로 로봇이 이미지 밖으로 나가면 임무는 실패한다.
• ($\langle subprogram\_w \rangle$:$\langle subprogram\_b \rangle$) --- 조건 연산. 로봇은 자신이 놓인 픽셀의 색을 확인한다. 흰색이면 $\langle subprogram\_w \rangle$를, 그렇지 않으면 $\langle subprogram\_b \rangle$를 실행한다.
• 0, 1, ..., 9 --- 인식 명령. 로봇은 자신이 어느 이미지 위에 있는지 알게 되면 이 중 하나를 실행하며, 그 즉시 프로그램이 종료된다.

각 이동 명령은 한 시간 단위가 걸린다. 조건 연산과 인식 명령은 즉시 수행된다.

프로그램이 올바르다는 것은, 로봇이 숫자 $i$의 이미지 위에 놓였을 때 실행이 항상 명령 i로 끝나는 것을 뜻한다. 올바른 프로그램들 중에서 최악의 경우 실행 시간 --- 가능한 $d$개의 시작 이미지에 대해 실행되는 이동 명령 수의 최댓값 --- 이 가장 작은 것을 생각하자. 이 최소 가능한 최악의 실행 시간을 구하여라.

첫째 줄에 세 정수 $d$, $h$, $w$가 주어진다($1 \le d \le 10$; $1 \le h, w \le 10$). 각각 이미지의 개수, 그리고 각 이미지의 높이와 너비이다.

이후에는 $d$개의 이미지 설명이 주어진다. 각 설명은 길이 $w$인 $h$개의 줄로 이루어지며, 모든 문자는 B(검은색) 또는 W(흰색)이다. 설명은 이미지 $0$부터 $d - 1$까지 순서대로 주어지며, 하나의 빈 줄로 구분된다.

올바른 인식 프로그램의 최소 가능한 최악의 실행 시간을 정수 하나로 출력한다.

그림은 로봇이 구별해야 하는 세 이미지의 예시를 보여 준다.