Snake

Time limit2sMemory limit1024 MB

Summary

Given a grid with a snake of up to 16 cells and one apple, decide whether the snake's head can reach the apple without hitting a wall or its own body.

Level: Medium6 of 10
Topics: DFS, Hash map, Simulation
Solved: No attempts yet

Problem

Google's version of Snake

Snake is a video game classic. The Museum of Modern Art (MoMA) preserves it, and it is listed as one of the 'Top 100 Video Games' of all time. The goal is to move the snake's head to an apple. When the snake reaches the apple, it eats it and grows longer. A new apple is then placed, and the longer snake must eat that one too.

The game is played on a grid, and each segment of the snake's body occupies one cell. The head can turn in three directions, but it cannot go backwards. The body follows the head. The head may not collide with the body or leave the grid. The whole snake moves at the same time, so the head may enter the cell that the tail is vacating.

The game requires quickness and foresight. As the snake grows, it becomes easier to make a turn that leaves the head doomed to hit a wall or its own body before it reaches the apple.

Write a program that determines whether the snake's head can reach the apple from a given position, or whether the snake is doomed to die.

Input

The first line contains two integers $r$ and $c$ ( $1≤r,c≤10$ , $r \cdot c≥2$ ), the number of rows and columns of the grid.

Each of the next $r$ lines contains a string of exactly $c$ characters from the set {'.', '0' to '9', 'a' to 'f', 'A'}. A '.' is an open cell. The hexadecimal digits '0' to '9' and 'a' to 'f' mark the snake, and 'A' marks the apple.

The snake is between 1 and 16 characters long. Its head is '0', and the other digits follow in strict order ('1' follows '0', '2' follows '1', and so on, with no skipped digits). Each digit appears at most once, each digit (except '0') is adjacent to the digit before it, and there is exactly one apple in the grid.

Output

Output a single integer. Print 1 if the snake's head can reach the apple, and 0 if it cannot and is doomed to die.

Examples4

Example 1

Input

5 8
......01
....98.2
...A.7.3
.....654
........

Expected output

Example 2
Input
```
5 4
...A
....
6789
5432
..01
```
Expected output
```
0
```
Example 3
Input
```
5 5
....A
.....
678..
54321
....0
```
Expected output
```
1
```
Example 4
Input
```
4 4
567A
4389
12ba
0dc.
```
Expected output
```
1
```