DWITE '08 R1 #3 - School's a maze

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, October 2008, Problem 3

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 are 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

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.