| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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 |
