2008 Canadian Computing Competition, Stage 1
Problem J3: GPS Text Entry
For her birthday, Sandy got a Global Positioning System (GPS) unit, which is an electronic device she can use to track the local hiking trails. Along the way Sandy can mark waypoints that can be recorded on a map when she gets home. A description of each waypoint can be entered in the unit, however the device does not have a keypad. Instead it has four cursor buttons, up, down, left, and right, and a button to accept the letter. The keypad looks like the following:
The screen displays a grid of the letters and symbols that can be used to “type out” the description.
Here is the layout of the grid:
When you enter the name of the waypoint, the cursor starts at the A. You must move the cursor to the location of the next letter or symbol and then accept that letter. The cursor can only move to squares which are adjacent horizontally or vertically (not diagonally). Once you have entered all the letters in the description, you need to move the cursor to ”enter” and accept the entire phrase.
You are to write a program that will calculate the number of cursor movements it takes to “type in” a phrase. For example, to enter the word “GPS”, starting from the “A” position, you would move down 1 to select “G”, then move right 3 and down 1 to select “P”, then move down 1 and left 3 to select “S” and finally move down 1 and right 5 to select “enter”. This is a total of 15 cursor movements. Note that the total number of cursor movements does not change if you choose to move down and then across or across and then down. Also note that you cannot move beyond the boundaries of the grid (e.g., you cannot move off the grid nor “wrap-around” the grid).
The input for your program will be a string of at most 40 characters. You may assume that all characters in the string are contained in the grid.
The output for your program will be an integer that is the total number of cursor movements needed to enter the string using the grid layout given.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
- String Manipulation
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3