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.|

P142SUMC - ROUND 2C - Trò chơi Snake

Chắc hẳn ai trong chúng ta cũng đã từng chơi trờ chơi điện tử di chuyển con rắn để ăn các quả táo. Bây giờ trò chơi sẽ được mô tả như sau: Màn hình sẽ là một bảng ô vuông hình chữ nhật kích thước n*m. Con rắn sẽ được mô tả bởi các con số 1, 2, 3…, đó là các khúc của con rắn, 1 là đầu, 2 là khúc sau, tiếp tục như vậy cho đến con số cuối cùng, đó là đuôi. Con rắn sẽ đi tiếp được sang các ô có chung cạnh với đầu của nó.

Tất nhiên là cũng như trò chơi mà chúng ta vẫn hay chơi nó không thể đi ra ngoài bảng hình chữ nhật, và nó sẵn chết nếu như đâm đầu vào đá (#) hoặc cắn phải chính nó (khi đầu nó trùng vị trí với một khúc thân khác của nó).

Trên bảng có một quả táo (@), giờ đây bạn hãy thử tìm xem mất ít nhất bao nhiêu được di chuyển để con rắn có thể ăn được quả táo. Một bước di chuyển là một lần đầu con rắn di chuyển sang một ô khác một cách hợp lệ.

Input

Dòng đầu tiên gồm 2 số nguyên n, m (1 <=n, m <=15).

n dòng sau, mỗi dòng gồm m kí tự mô tả bảng ô vuông hình nhữ nhật.

Với các số nguyên thể hiện thể con rắn, các số nguyên này không vượt quá 9, “#” là đá và “@” là quả táo.

Output

In ra số bước di chuyển ít nhất để con rắn có thể ăn được táo. Nếu không có cách di chuyển nào in ra “-1”.

Example

Test 1:

Input:

4 5

##...

..1#@

432#.

...#.

Output:

4

 

Test 2:

Input:

4 4

#78#

.612

.543

..@.

Output:

6

 

Test 3:

Input:

3 2

3@

2#

1#

Output:

-1


Được gửi lên bởi:adm
Ngày:2014-07-01
Thời gian chạy:3s
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 JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-07-25 07:45:45 Hat Dau Nho
test 2 ran lam sao di chuyen dc nhi :|
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.