QCJ1 - Mountain Walking

In this problem your task is to program a robot that will output some data about a terrain after traversing it. Input will be in the form a 2D picture containing only 4 types of characters:

  • '/' : Forward slash, indicating ascent.
  • '\' : Backward slash, indicating descent.
  • '_' : Underscore, denoting horizontal plane.

Additionally there will be only SPACE (Ascii value = 32) characters. (Refer to the below figure).

The robot starts its journey at bottom left corner of the terrain and after traversing stops at the bottom right corner. Also note that the robot will always start and end at the SAME LEVEL.

Given the picture as input you will have to output 2 things. The "Total Walk Distance" i.e, the total length of the path and the type of steps taken to complete the Journey. For the sake of simplification we will assume that each character ('/' , '\' and '_') has length = 1.

Now Consider the following example:

       _
      / \/\
     /     \
    /       \

The robot starts at the bottom left corner and takes the following path:

  1. Ascends 3 steps
  2. Moves forward by 1 step
  3. Descends 1 step
  4. Ascends 1 step
  5. Descends 3 steps

and robot ends it journey at bottom right corner (At the same level). The Total Walk Distance = 9.

Input

First line of input will be an integer N (N < 20). The next line will be an empty. Then exactly N lines follow describing the terrain.

You can assume the following for the input (terrain).

  • Input will contain only four types of characters (" ", "_", "/", "\").
  • The terrain will start and end at the same level.
  • Each line is guaranteed to have at least one non white space character.
  • Maximum width of any line won't be larger than 200.
  • There will be no trailing white spaces.

Output

First line of output should be the Total Walk Distance followed by the description of the terrain. Each line must be ONE of the following

  • Up xx steps
  • Down xx steps
  • Walk xx steps

Where xx is an integer. Refer to the examples for exact specification.

Example

Input:
3

  /\
 /  \
/    \

Output:
Total Walk Distance = 6
Up 3 steps
Down 3 steps
Input:
2
 _____  ___
/     \/   \

Output:
Total Walk Distance = 12
Up 1 steps
Walk 5 steps
Down 1 steps
Up 1 steps
Walk 3 steps
Down 1 steps
Input:
5

        _
   /\__/ \
  /       \
 /         \/\_
/              \

Output:
Total Walk Distance = 16
Up 4 steps
Down 1 steps
Walk 2 steps
Up 1 steps
Walk 1 steps
Down 3 steps
Up 1 steps
Down 1 steps
Walk 1 steps
Down 1 steps

Added by:abhijith reddy d
Date:2010-02-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Own

hide comments
2010-02-04 15:18:45 numerix
@scrooge: Read the description!
2010-02-03 19:53:00 vimal raj sharma old account
USE two while loops to handle empty line
after inputting number of lines

while( (c = getchar() ) != '\n');
while( (c = getchar() ) != '\n');

2010-02-03 12:30:26 scrooge
Is this a valid test case?:
2

\
/
2010-02-03 07:19:12 rozuur
second line in the input is not necessarily a newline, it may also contain white space characters.
Got AC after reading second line with gets instead of getchar
2010-02-02 15:53:15 abhijith reddy d
@ Ehor Nechiporenko : NO
2010-02-02 12:47:39 [Rampage] Blue.Mary
Er, I think if you omit all the assumptions except the one about the length of the line, you'll get Accepted quicker.

Edit: I do think the sample lead me to several Wrong Answers. So, use the following to get the input:

while(gets(s)){...}

For the first line, which contains "the number of lines following", you may just omit it.

Last edit: 2010-02-02 13:02:18
2010-02-02 10:50:44 Ehor Nechiporenko
Could picture has level less then level of start point?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.