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.

Copyright (c) IARCS 2003-2018; Last Updated: 25 Nov 2004