ALCATRAZ4 - THE SHORTEST PATH

no tags 

YOU ARE GIVEN A 2D GRID WITH EACH CELL CONTAINING AN ALPHABET , YOU HAVE TO START AT ANY POINT AND MOVE EITHER UP,DOW,LEFT AND RIGHT TO CREATE THE WORD "ALCATRAZ" BY PICKING UP ALPHABETS IN ORDER  . AFTER CHOOSING AN ALPHABET , IT GETS REMOVED FROM THERE AND LEAVES AN EMPTY CELL BEHIND . YOU HAVE TO TELL THE MINIMUM NUMBER OF MOVES NEEDED TO DO SO 

Input

2 SPACE SEPERATED INTEGERS N,M ( ROWS AND COLUMNS RESPECTIVELY ) 

1<=  N,M <=500

THEN NEXT N LINES GIVES THE DETAILS OF THE MAZE 

Output

THE SHORTEST PATH AS DESCRIBED IN THE ABOVE PROBLEM 

PRINT "IMPOSSIBLE" (WITHOUT QUOTES) IF YOU CAN'T MAKE UP THAT WORD .

Example

Input:
4 5
AZCLT
AARAL
SJATC
LARAZ
Output:
9
PATH IS AS FOLLOWS : 2,4 - 2,5 - 3,5 - 3,4 - 3,3 - 3,4 - 4,4 - 4,3 - 4,4 - 4,5  

hide comments
Vipul Srivastava: 2017-06-16 22:34:01

Last edit: 2017-06-16 22:37:23
Vipul Srivastava: 2017-06-15 21:35:09

how can we get 'L' after 'A' in Blue.Mary's test case?

Re :- move down then right :)

Last edit: 2017-06-16 09:29:20
[Rampage] Blue.Mary: 2017-06-15 16:38:26

What's the answer for this test case:

8 8
AUUUUUUU
UAUUUUUU
UUAUUUUU
UUULUUUU
UUUUCUUU
UUUUUTUU
UUUUUURU
UUUUUUUZ

BTW, please make sure your test cases are right.

Re : 42 . Test cases were confirmed again .

Last edit: 2017-06-15 18:23:14
Vipul Srivastava: 2017-06-15 07:51:57

in what directions can he traverse?

Re : Read the problem statement again . sorry for inconvenience

Last edit: 2017-06-15 18:24:04

Added by:Alcatraz
Date:2017-06-14
Time limit:0.293s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All