VUKVN - ICEFROG
Giới hạn- Thời gian: 0.025s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Chú chó sói Vjekoslav đang chạy trốn khỏi một đám thợ săn khát máu. Những người thợ săn rất thông minh và họ đang nấp sau những cái cây. Vjekoslav biết điều đó, nhưng không biết chính xác cây nào. Con sói muốn về nơi ở của nó một cách an toàn nhất , tức là càng xa cây càng tốt !
Khu rừng có thể được mô tả bằng một hình chữ nhật kích thước N*M. Những ô trống được đánh dấu bằng ký hiệu '.' , những ô có cây là '+' , vị trí ban đầu của Vjekoslav là 'V' và nhà của nó là 'J'. Vjekoslav có thể chạy từ ô nó đang đứng đến 4 ô chung cạnh xung quanh nó đứng.
Nếu Vjekoslav đang ở ô (R,C) và có một cái cây ở ô (A,B) thì khoảng cách được tính theo công thức :|R-A| + |C-B|. Hãy giúp Vjekoslav tìm đường đi an toàn nhất để về nhà . Đường đi an toàn nhất được hiểu là đường đi mà khoảng cách bé nhất từ một ô nào đó trên đường đi đó đến tất cả các cây là lớn nhất.
Input
Dòng đầu tiên là hai số N,M (0<N,M <=500) là kích thước của khu rừng.
N dòng sao mỗi dòng gồmN ký tự thuộc tập {'+','.','V','J'} mô tả khu rừng.
Input luôn đảm bảo chứa một ký tự 'V', 1 ký tự 'J' và ít nhất một ký tự '+'.
Output
Gồm một dòng duy nhất là kết quả.
Example
Input:
4 4
+...
....
....
V..J
Output:
3
Input
4 5
.....
.+++.
.+.+.
V+.J+
Output
0.
- Người up: company_1
- Nguồn bài: COCI 09