COCI 2008/2009, Croatian Regional

Task CIJEVI

To help design the new gas pipeline which will be used to deliver Russian gas to Croatia, Zagreb and Moscow are using the computer game Pipe Mania. In the game, Europe is divided into R rows and C columns. Each cell can be empty or contain one of the seven basic pipeline building blocks:

Gas flows from Moscow to Zagreb. Gas can flow in either direction through the building blocks.
Block '+' is special in that gas must flow in two directions (one vertical, one horizontal), as in the following example:

Work on the new pipeline had already started when it was found that malicious hackers got hold of the plan and erased exactly one building block from the plan i.e. replaced it with an empty cell.

Write a program that determines where the block was erased from and what type it was.

Input

The first line contains two integers R and C, the dimensions of Europe (1 ≤ R, C ≤ 25).

The following R lines contain the plan, each consisting of exactly C characters. The characters are:

• Period ('.'), representing an empty cell;
• The characters '|' (ASCII 124), '-', '+', '1', '2', '3', '4', representing the building block types;
• The letters 'M' and 'Z', representing Moscow and Zagreb. Each of these will appear exactly once in the plan.

The flow of gas will be uniquely determined in the input; exactly one building block will be adjacent to each of Moscow and Zagreb. Additionally, the plan will not have redundant blocks i.e. all blocks in the plan must be used after the missing block is added.

The input will be such that a solution will exist and it will be unique.

Output

Examples

3 7
.......
.M-.-Z.
.......

2 4 -

3 5
..1-M
1-+..
Z.23.

2 4 4

6 10
Z.1----4..
|.|....|..
|..14..M..
2-+++4....
..2323....
..........

3 3 |

All Submissions
Best Solutions

Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M
Added: Apr 29, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)