Mô tả và yêu cầu

Bản đồ

Trong một vùng biển của quốc gia Alabasta có 2 hòn đảo chính với dân cư đông đúc. Để
tăng cường sự giao thương giữa 2 đảo này, chính phủ quyết định xây dựng 2 bến cảng lớn
đặt tại 2 đảo cho 2 nước này. Vấn đề đặt ra là làm sao có thể chọn địa điểm xây dựng 2 bến
cảng sao cho đường đi giữa 2 bến cảng là nhỏ nhất có thể.
Bản đồ về vùng biển và 2 hòn đảo này đã được mã hóa thành một bảng hình chữ nhật gồm
m x n ô vuông đơn vị như sau:
- Ô vuông đơn vị được ký hiệu “X” thuộc đất liền.
- Ô vuông đơn vị được ký hiệu “.” thuộc vùng biển.
Hai ô vuông thuộc cùng một vùng đất nếu chúng có chung một cạnh. Đường đi giữa 2 bến
cảng được mô tả là 1 dãy các ô chung cạnh trên vùng biển nối liền 2 đảo, độ dài của đường
đi là số ô mà nó đi qua.
Yêu cầu: Tìm khoảng cách ngắn nhất có thể của đường đi nối liền 2 bến cảng.
Dữ liệu vào: cho trong file văn bản map.out có cấu trúc như sau:
- Dòng đầu tiên ghi 2 số nguyên dương m và n cho biết số dòng và số cột của bản đồ
đã mã hóa (1 ≤ m, n ≤ 50).
- m dòng tiếp theo, mỗi dòng ghi n ký tự, mỗi ký tự hoặc “X” hoặc “.” cho biết thông
tin về bản đồ.
Kết quả: ghi ra file văn bản map.out gồm 1 số duy nhất là độ dài nhỏ nhất tìm được.

Ví dụ

map.inp                   map.out                 Giải thích
          6 16                      3                       ................
          ................                                  ..1111....222...
          ..XXXX....XXX...                                  ...1111X...22...
          ...XXXX....XX...                                  .1111..XX..222..
          .XXXX......XXX..                                  ........22222...
          ........XXXXX...                                  .........222....
          .........XXX....
                                                            1 và 2 cho biết 2 đảo.
                                                            X cho biết 1 trong các
                                                            đường ngắn nhất tìm được.