Indian National Olympiad in Informatics

Related:

Online Programming Contest, 6-7 November 2004

IARCS home > OLYMPIAD

Basic Division

Problem 2: The Medu Vada Maze, (K Narayan Kumar, CMI)

A maze, for our purposes, consists of a rectangular grid of cells, where some of the cells are blocked and the remaining cells are empty. A mouse is placed in one of the empty cells and a dosa is placed at a different empty cell. From a cell, the mouse can move to any empty neighbouring cell according to the rules given below. Your aim is to determine whether the mouse can walk through this maze and reach the dosa.

A maze with R rows and C columns will be presented as a sequence of R lines, each with C characters. The character # denotes a blocked cell and the character . denotes an empty cell). The mouse and the dosa sit in distinct empty cells and those cells are marked by M and D instead of .

Here is a maze with 6 rows and 12 columns.

####.#..####
.M.#..#..D.#
#.#...#....#
...#..#..#..
...#.#.###.#
.........###

We will refer to a cell by its row and column position. The rows are numbered from top to bottom and the columns from left to right. For example, in the maze above, the mouse is initially placed at postion (2,2) indicating second row and second column and the dosa is at position (2,10) indicating second row and tenth column.

The mouse can move from a cell to the one above it, the one below it, the one to its left or the one to its right. Further, from a cell in the leftmost column the mouse can move to the cell in the same row in the rightmost column and from a cell in the rightmost column it can move to the cell in the same row in the leftmost column. Similarly, from a cell in the top row the mouse can move to the cell in the same column in the bottom row and from a cell in the bottom row it can move to the cell in the same column in the top row. Thus, in the maze above, the mouse can move from (4,1) to (4,12) and from (6,5) to (1,5) and so on.

You should think of the maze as having the shape of a solid ring, like a Medu Vada. It is as if the paper on which the Maze is drawn is rolled back and stuck at the edge so that the bottom row touches the top row. The resulting cylinder is rolled around so that the right and left columns, which now form circles, touch each other. Thus, the left most column and right most column touch each other, as do the top row and the bottom row.

In the example above, the mouse can reach the dosa by walking through the following sequence of cells: (2,2), (3,2), (4,2), (4,1), (4,12), (4,11), (3,11), (3,10) and (2,10). This path is marked with with x's below:

####.#..####
.M.#..#..D.#
#x#...#..xx# 
xx.#..#..#xx
...#.#.###.# 
.........###

Alternatively it can also take the following path:

####.#.x####
.M.#..#xxD.#
#x#...#....# 
.x.#..#..#..
.x.#.#.###.#
.xxxxxxx.###

Your task is to determine whether it possible for the mouse to reach the dosa.

Input format

The first line of the input will contain two numbers R and C denoting the number and rows and columns respectively. This is followed by R lines, each with C characters, each of which is # or . or M or D. There is exactly one M and one D in the input.

Output format

If there is no path from the mouse to the dosa print a single line containing the word NO. If there are paths from the mouse to the dosa, then the first line of the output should consist of the word YES. Following this must be R lines of C characters each, where each character is # or . or x or M or D, describing a path from M to D using the x's as illustrated above. There may be many paths and it suffices to describe one path.

Test Data

In all the inputs, R ≤ 1000 and C ≤ 1000. Further, in 80% of the inputs, 3 ≤ R ≤ 60 and 3 ≤ C ≤ 60.

Example

We now illustrate the input and output formats using some examples.

Sample input 1:

6 12
####.#..####
.M.#..#..D.#
#.#...#....#
...#..#..#..
...#.#.###.#
.........###

Sample output 1:

YES
####.#..####
.M.#..#..D.#
#x#...#..xx#
xx.#..#..#xx
...#.#.###.#
.........###

Sample input 2:

4 6
##.#..
.M.#.#
#.#.D.
...#.#

Sample output 2:

NO

Test data:

10 zipped test inputs and outputs
Some test inputs admit multiple correct solutions. Here is a C program to check if a given output is correct for a given input.