Có một số con cừu trong trại chăn nuôi của Mickey. Trong khi Mickey đang ngủ say, những con sói đói đã vào trại và tấn công đàn cừu.
Trại có dạng hình chữ nhật gồm các ô tổ chức thành hàng và cột. Kí tự dấu chấm .
là ô rỗng, kí tự #
là hàng rào, kí tự o
là cừu và kí tự v
là chó sói.
Chúng ta coi ~2~ ô là cùng một miền nếu có thể chuyển từ ô nọ tới ô kia bằng đường đi chỉ gồm các đường đi theo chiều ngang hoặc thẳng đứng không vướng hàng rào. Các ô mà từ chúng có thể thoát khỏi sân không được xem là một phần của bất kì miền nào.
May thay, những con cừu biết tự vệ. Chúng có thể chiến đấu với những con sói trong miền (húc chết sói) nếu số lượng cừu lớn hơn số lượng sói trong cùng một miền. Ngược lại những con sói sẽ ăn hết các con cừu trong cùng một miền.
Ban đầu các con cừu và các con sói đã được xác định trong các miền của trại.
Viết một chương trình tính số lượng cừu và số lượng sói còn lại trong sáng hôm đó.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên ~R~ và ~C~, ~3 \leq R, C \leq 250~ là số hàng và số cột của trại. Mỗi dòng trong ~R~ dòng sau gồm ~C~ kí tự. Tất cả các kí tự này biểu diễn các vị trí có hàng rào, cừu và chó sói trong trại.
Kết quả ra:
Chỉ một dòng gồm ~2~ con số: số cừu và số sói còn lại trong trại.
Sample Input
8 8
.######.
#..o...#
#.####.#
#.#v.#.#
#.#.o#o#
#o.##..#
#.v..v.#
.######.
Sample Output
3 1
*Nguồn: Hồ Sĩ Đàm - Trần Đỗ Hùng, "Chuyên đề bồi dưỡng HSG Tin học THPT Ứng dụng lí thuyết đồ thị", NXB Giáo Dục *
Comments