Nối Ba 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 ba vùng.

Hãy tìm số lượng ô . tối thiểu cần tô thành X để nối cả ba 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 ba 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....XXX....	4	Cần tô thêm 4 ô để nối ba vùng thành một

Bình luận

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