ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1912. Titan Ruins: Passing through Walls

Time limit: 1.0 second
Memory limit: 64 MB
Soren opened his eyes with an effort but this didn't help much—there was a deaf darkness around. An unbearable pain in the back of his head prompted that he had hit his head in the fall. Spreading his arms he realized that he was in a very small room without any openings. Luckily, the wand was intact, which meant that Soren could still use magic.
Casting the Scanning Spell, he discovered disappointingly that identical small square rooms with solid walls were spreading evenly in all directions. There was only one thing to be glad about—Alba, still alive, was in the adjoining room. Soren contacted him telepathically.
`Are you alright?'
`Have you got any ideas on how to get out of here?'
`There's no way out through the top, but we can try passing through the walls. Some of them are thinner than others. If we combine our powers, we can take one of us through a thin wall. It's a pity the rooms are so small—we can't get into the same room together. And we always have to stay in rooms that have at least one common corner so that we can keep contact. It'll be hard, but let's try.'
Soren draw a scheme of all the rooms and marked thin and thick walls. It turned out that all the rooms together formed a large rectangle, around which there were no walls, so that it was possible to move freely anywhere outside the rectangle. Now Alba and Soren had to understand how they should move between the rooms to get both of them out of the trap.


The first line contains the dimensions of the rectangle n and m (2 ≤ n, m ≤ 250). In the following 2n + 1 lines you are given a scheme of the trap. There are 2m + 1 symbols in each line. Soren and Alba are denoted by the symbols “1” and “2”; their rooms have at least one common corner. The symbols “|” and “-” denote thick walls. The symbols “.”, “+”, and “ ” denote thin walls, corners, and empty rooms, respectively.


If Soren and Alba can't get out of the trap, output the line “Death”. Otherwise, output the minimum number of passages through thin walls that Soren and Alba must make to free themselves.


3 4
| . .1. |
| .2. . |
| . | | |
2 2
| | |
Problem Author: Stanislav Vasilyev (prepared by Denis Mukhametianov)
Problem Source: NEERC 2012, Eastern subregional contest