ALCATRAZ4 - THE SHORTEST PATH

You are given a 2D grid with each cell containing a letter, you have to start at any point and move either up, down, left and right to create the word "ALCATRAZ" by picking up letters in order. After choosing a letter, it gets removed and leaves the cell empty. You have to determine the minimum number of moves needed to do so.

Input

2 space separated integers N, M (number of 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 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


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

hide comments
2017-08-24 14:42:12
Loved it... GG ALCATRAZ
Re : How did you know that I'm a gamer ?
-> Re: Well, I guess that I have pulled a hypothesis that most of the coders are also gamers?? hahaha lucky guess
- - >Re: Haha true that XD!!!

Last edit: 2018-05-08 21:30:27
2017-06-15 21:35:09 Vipul Srivastava
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
2017-06-15 16:38:26 [Rampage] Blue.Mary
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
2017-06-15 07:51:57 Vipul Srivastava
in what directions can he traverse?

Re : Read the problem statement again . sorry for inconvenience

Last edit: 2017-06-15 18:24:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.