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

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.