Image Recognition

Time limit1sMemory limit128 MB

Summary

Design an optimal decision program for a robot that moves on a grid and reads pixel colors to identify which of d given images it starts on, minimizing worst-case movement steps.

Level: Hard8 of 10
Topics: BFS, Graph, Brute force, Simulation
Solved: No attempts yet

Problem

Irene works for Novel Efforts in Effective Recognition of Characters (NEERC). Her new project concerns image recognition using robots.

She starts with a very simple model. There are $d$ fixed images, called digits $0$ to $d - 1$ . Each image is a $w \times h$ rectangle of white and black unit squares (pixels). All images are distinct (every two images differ in at least one pixel).

A robot is placed on the upper-left pixel of one of the images and runs a program written in the language below. Its task is to recognize which of the $d$ images it was placed on.

The programming language consists of the following commands:

U, D, L, R --- movement commands. The robot moves one pixel up, down, left, or right. If a movement would take the robot outside the image, the task fails.
( $\langle subprogram\_w \rangle$ : $\langle subprogram\_b \rangle$ ) --- conditional. The robot checks the color of the pixel beneath it. If it is white then $\langle subprogram\_w \rangle$ runs, otherwise $\langle subprogram\_b \rangle$ runs.
0, 1, ..., 9 --- recognition commands. The robot executes one of these once it knows which image it is on; the program then terminates.

Each movement command takes one time unit. Conditionals and recognition commands are instantaneous.

A program is correct if, whenever the robot is placed on the image of digit $i$ , execution ends with the command i. Among all correct programs, consider the one whose worst-case execution time --- the maximum number of movement commands executed over the $d$ possible starting images --- is as small as possible. Determine this minimal possible worst-case execution time.

Input

The first line contains three integers $d$ , $h$ , and $w$ ( $1 \le d \le 10$ ; $1 \le h, w \le 10$ ) --- the number of images, and the height and width of each image.

The rest of the input contains $d$ image descriptions. Each description has $h$ lines of length $w$ , where every character is B (black) or W (white). Descriptions are given in order from image $0$ to image $d - 1$ and are separated by a single empty line.

Output

Print a single integer: the minimal possible worst-case execution time of a correct recognition program.

Notes

The figure shows three example images that the robot must distinguish.

Examples4

Example 1

Input

3 5 4
WBBW
BWWB
BWWB
BWWB
WBBW

WWBW
WBBW
BWBW
WWBW
WWBW

WBBW
BWWB
WWBW
WBWW
BBBB

Expected output

Example 2
Input
```
2 1 1
W

B
```
Expected output
```
0
```
Example 3
Input
```
2 1 3
WWB

WWW
```
Expected output
```
2
```
Example 4
Input
```
2 2 2
BW
WW

WW
WW
```
Expected output
```
0
```