Problem M
Snake
The game is played on a grid, and every segment of the snake’s body occupies one cell. The snake’s 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 exit the grid. Since the entire snake moves at the same time, the head is allowed to enter the cell that the tail is vacating, unless doing so would cause the snake’s head to move backwards. A snake consisting of just the head (with no other body parts) may move in any direction.
Playing the game requires quickness and foresight. It’s all too easy to take turns that put the snake head in a position where it’s doomed to hit the wall or its body before reaching the apple, especially as the snake grows longer.
You’re being asked to write a program that can determine whether the snake’s head can reach the apple from a given position, or not and the snake is doomed to die.
Input
The first line of output contains two integers
Each of the next
where ‘.’ represents an open cell
in the grid, the hexadecimal digits ‘0’,
Output
Output a single integer, which is
Sample Input 1 | Sample Output 1 |
---|---|
5 8 ......01 ....98.2 ...A.7.3 .....654 ........ |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
5 4 ...A .... 6789 5432 ..01 |
0 |
Sample Input 3 | Sample Output 3 |
---|---|
5 5 ....A ..... 678.. 54321 ....0 |
1 |
Sample Input 4 | Sample Output 4 |
---|---|
4 4 567A 4389 12ba 0dc. |
1 |