Kết Bạn Qua Cỏ

Đ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 một lưới $N \times M$ ô, mỗi ô là một trong ba loại:

C: ô có bò
G: ô có cỏ
.: ô trống

Hai con bò có thể kết bạn bằng cách gặp nhau tại một ô cỏ kề cạnh (chung cạnh) với cả hai. Mỗi ô cỏ chỉ được sử dụng một lần. Mỗi lần sử dụng một ô cỏ, nó tạo ra đúng một cặp bạn.

Hãy tìm số cặp bạn nhiều nhất có thể tạo ra.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$
$N$ dòng tiếp theo: Chuỗi $M$ ký tự mô tả lưới

Dữ liệu ra

Một số nguyên duy nhất: số cặp bạn nhiều nhất.

Ràng buộc

$1 \leq N, M \leq 1000$

Ví dụ

Input	Output	Giải thích
4 5 .CGGC .CGCG CGCG. .CC.C	4	Có thể tạo 4 cặp bạn: (2,2)-(3,3) qua cỏ (3,2); (2,2)-(2,4) qua cỏ (2,3); (2,4)-(3,3) qua cỏ (3,4); (2,4)-(1,5) qua cỏ (2,5).

Bình luận

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