Du Lịch Đảo

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có một lưới $R \times C$ gồm các ô: X (đảo), S (nước nông), . (nước sâu). Các ô X liên thông (theo 4 hướng) tạo thành một đảo. Có tổng cộng $N$ đảo.

Bessie xuất phát từ một đảo bất kỳ và muốn thăm tất cả $N$ đảo. Di chuyển giữa các đảo phải đi qua các ô S (không thể đi qua .). Chi phí di chuyển là số ô S phải bơi qua.

Tìm tổng chi phí bơi tối thiểu để thăm tất cả các đảo.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $R$ và $C$ .
$R$ dòng tiếp: Mỗi dòng gồm $C$ ký tự (X, S, hoặc .).

Dữ liệu ra

Một số nguyên — tổng chi phí bơi tối thiểu.

Ràng buộc

$1 \leq N \leq 15$ (số đảo)
$1 \leq R, C \leq 50$

Ví dụ

Input	Output	Giải thích
5 4 XX.S .S.. SXSS S.SX ..SX	3	Bơi 1 ô từ đảo 1 đến đảo 2, rồi 2 ô đến đảo 3. Tổng = 3.
5 5 XSSSX ....S XSSSX S.... XSSSX	11

Bình luận

Không có bình luận tại thời điểm này.