Nối Hai Vùng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Cho lưới $N \times M$ gồm các ký tự X và .. Các ô X liền kề theo chiều ngang hoặc dọc tạo thành một vùng liên thông. Đảm bảo lưới có đúng hai vùng.

Hãy tìm số lượng ô . tối thiểu cần tô thành X để nối hai vùng thành một.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$
$N$ dòng tiếp theo: Mỗi dòng chứa một xâu $M$ ký tự gồm X và .

Dữ liệu ra

In ra một số nguyên — số ô tối thiểu cần tô thêm.

Ràng buộc

$1 \leq N, M \leq 50$
Lưới có đúng hai vùng liên thông gồm các ô X

Ví dụ

Input	Output	Giải thích
6 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....	3	Cần tô thêm 3 ô để nối hai vùng
10 16 ...XXXXXXXXXX... ...X........X... ...X........X... ...X........X... ...X...XXX..X... ...X..XXXX..X... ...X........X... ...X........X... ...X........X... ...XXXXXXXXXX...	2	Vùng nhỏ nằm trong vùng lớn, cần tô 2 ô

Bình luận

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