DWITE Online Computer Programming Contest
October 2008
Problem 3
School's a maze
#########A#########
#...#.........#...#
#...#.#######.#...#
#..B#.#FGHIJ#.#E..#
#.................#
#####.#######.#####
#.....#.....#.....#
#..C#.#.....#.#D..#
#...#.#.....#.#...#
#####K#######L#####

Given this overly-imaginative layout of a tiny 5-room floorplan (one of which happens to be missing a door), the 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 periods (.) and letters. There are no diagonal movement. For reference: The 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 file DATA3.txt will contain 10 lines, a copy of the same map as presented above. It will be followed by 5 more lines, each being a string made up of the aforementioned capital letters (ABCDEFGHIJKL), 1 <= N < 20 in length, describing the schedule.

The output file OUT3.txt will contain 5 lines -- the 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