Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ALGOPRO1 - Mê cung Laze

Standard mazes lose their mystery as one grows older. But throw in some lasers, and suddenly you've got yourself a recipe for cross-generational appeal. The object in any maze is to find your way from your starting point to some goal. In a Laser Maze you must additionally contend with laser turrets.

A laser turret is a stationary pillar that both blocks your movement and fires lasers from one side. Every time you take a step (either up, down, left, or right), every laser turret in the maze then rotates 90 degrees clockwise, and then shoots a momentary laser blast in the direction that it is facing. Needless to say, if you find yourself in the path of one of these lasers, you won't be around long enough to find a way out. A wall is a stationary pillar that blocks your movement, but does not fire lasers.

Lasers are powerful, but they do not pass through walls or laser turrets. The laser turrets respond to your movements, so you can't stand still and wait for the turrets to turn. If you reach the goal, but are immediately shot by a laser, your efforts will have been in vain, so make sure you reach the goal safely.

Input

Input begins with an integer T, the number of mazes you'll explore. For each maze, there is first a line containing two integers, M and N, the height and width of the maze, respectively. The next M lines contain N characters each, describing the maze:
. (empty space)
# (wall)
S (starting position)
G (goal)
< > ^ v (laser turrets)

The four symbols for laser turrets signify turrets that are initially pointing left, right, up, or down respectively before you take your first step.

Output

For the ith maze, print a line containing "Case #i: " followed by the smallest number of steps necessary to get to the exit without being hit by a laser, or the string "impossible'' if there is no way to reach the goal safely.

Constraints
1 ≤ T ≤ 100
1 ≤ M, N ≤ 100
Each maze will contain exactly one 'S' and exactly one 'G'.

Example

Input:
5
2 5
##^##
S...G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G Output: Case #1: 6
Case #2: 4
Case #3: 3
Case #4: impossible
Case #5: 8

Được gửi lên bởi:adm
Ngày:2015-01-30
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:Facebook Hacker Cup 2015 Qualification

hide comments
2015-05-01 14:46:14 Nguyễn Vĩnh Thịnh
:)

Last edit: 2017-02-22 10:33:31
2015-02-04 14:34:14 Xiao Lang
:3
2015-02-02 14:20:58 Black Hole
sai 1 ký tự :/
2015-02-01 16:54:19 Cường D14AT1
Một kết cục chết chóc!
2015-01-31 18:23:48 Black Hole
Case # @@
Đọc ko kĩ in ra toàn Case thiếu dấu '#' mà ko biết sai đâu :'(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.