| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P147PROF - ROUND 7F - Trò chơi tìm đường |
Cho một bảng kích thước M x N. Ban đầu có một số ô được đánh dấu là vật cản (màu đen trong hình), các ô còn lại là ô trống. Người chơi được chọn trước vị trí xuất phát cho quả bóng trên một ô trống nào đó. Nhiệm vụ là cần đưa quả bóng đi qua tất cả các ô trống của bảng bằng cách đi lên, xuống, trái, phải. Nhưng, nếu va chạm với vật cản thì quả bóng sẽ dừng lại. Mỗi lần thay đổi hướng đi sẽ được tính là 1 bước. Bài toán đặt ra là tìm số bước tối thiểu để có thể thắng cuộc với một cặp số M và N cho trước. Ví dụ trong hình, số bước tối thiểu là 10.
Input
Mỗi bộ test bắt đầu bằng một dòng ghi 2 số M và N cách nhau một khoảng trống (1<=M,N<=30). M dòng tiếp theo, mỗi dòng ghi N ký tự. Trong đó ký tự "*" là ô có vật cản, còn ký tự "." là ô trống. Input kết thúc khi gặp M = N = 0.
Output
Với mỗi bộ test, ghi ra màn hình số thứ tự bộ test và giá trị số bước tối thiểu tìm được. Nếu không có cách nào để thắng cuộc, ghi ra giá trị -1.
Example
Input: 5 5
**...
.....
....*
..*..
.....
0 0 Output: 10
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-21 |
| Thời gian chạy: | 5s |
| 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 |
