Bài viết sưu tầm

ICEFROG 

(Nguồn bài: CROATIAN OPEN 2009)

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.

Dữ liệu vào: Đọc từ file ICEFROG.INP 

- 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 sau mỗi dòng gồm N 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', một ký tự 'J' và ít nhất một ký tự '+'.

Kết quả: Gồm ra file ICEFROG.OUT một dòng duy nhất chứa số nguyên là kết quả.

Ví dụ:

Hướng dẫn:

Cách làm tương tự như bài trên, kết hợp Loang với chặt nhị phân khoảng cách.