Programming Geek
Rated 4.7/5 based on 1446 reviews

### TCS CodeVita 2015 Round 2 : Romeo and Juliet

Problem : Romeo and Juliet

Romeo and Juliet stay in Rectanglevilla. As the name suggests, Rectanglevilla is indeed a rectangle in shape. Romeo's current location is marked by 's'. Juliet's current location is marked by 'd'. In a difficult hour, Romeo has to ensure that he reaches Juliet via the shortest path and hence in shortest time.

There are many in Rectanglevilla who are enemies of Romeo and hence will not allow Romeo to pass through their areas. Romeo must avoid these areas while reaching out for Juliet. These areas are marked by 'w' character. Areas that Romeo can freely access is marked by '-' character.

Today Romeo needs your help to reach Juliet via shortest path. Help him.

The input and output specification sections describe how inputs will be provided on console and how output is expected back on console.
Input Format:
1. First line of input contains grid dimensions delimited by space character
2. Next rows number of lines contain column number of characters
3. Valid characters are {s, d, w, -}, where
1. s represents the location of the Romeo
2. d represents the location of the Juliet
3. w represents inaccessible region
4. - represents accessible region
4. End of input is marked by -1 character

Output Format:
1. Output grid should be of the same dimension as the input grid
2. Output grid should contain path from Romeo's location s to Juliet's location d
3. The 's' character in the grid must be replaced by character 'a' to denote that Romeo is actively heading towards Juliet.
4. See example section for better understanding

Constraints:
1. It is guaranteed that there will always be exactly one shortest path for Romeo to reach Juliet

Sample Input and Output

SNo.InputOutput
1
4 4
w - d -
w - w -
w - w w
s - - -
-1

w - d -
w a w -
w a w w
a - - -
2
6 6
s - - - - w
- - - - w -
- - - w - -
- - w - - -
- w - - - -
w - - - - d
-1

a - - - - w
- a - - w -
- - a w - -
- - w a - -
- w - - a -
w - - - - d

Explanation for sample input and output 1:

Figure 1.

Note: - The output format shown above is for understanding purpose such that it highlights the shortest path between Romeo and Juliet. The example in above table depicts output in text format as you will be required to provide.
Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.
Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc
Note:

For C and C++, return type of main() function should be int.