DWITE Online Computer Programming Contest, October 2008, Problem 3

#########A#########
#...#.........#...#
#...#.#######.#...#
#..B#.#FGHIJ#.#E..#
#.................#
#####.#######.#####
#.....#.....#.....#
#..C#.#.....#.#D..#
#...#.#.....#.#...#
#####K#######L#####

Given this overly imaginative layout of a tiny 5 room (1 of which happens to be missing a door) floorplan; letters ABCDEFGHIJKL mark the points of interest. Given a daily schedule, as a sequence of letters, how much would one have to walk, while taking the most optimal paths?

Walking is done on . (period)s and letters. There is no diagonal movement. For reference: distance between B to F is ~6~. From F to J is ~4~. And so the path BFJE will be ~16~. If a letter is consecutively followed by itself (such as BB), the distance is ~0~.

The input will contain 10 lines, a copy of the same map as presented above. It will be followed by 5 more lines, each a string made up of mentioned capital letters (ABCDEFGHIJKL), ~1 \le N < 20~ in length, describing the schedule.

The output file will contain 5 lines – optimal distance travelled, for the plan specified.

Sample Input

#########A#########
#...#.........#...#
#...#.#######.#...#
#..B#.#FGHIJ#.#E..#
#.................#
#####.#######.#####
#.....#.....#.....#
#..C#.#.....#.#D..#
#...#.#.....#.#...#
#####K#######L#####
A
ABBB
ABCK
FGHIJ
KEBK

Sample Output

0
11
25
4
38

Problem Resource: DWITE