USACO 2014 - Cow Art
Xem PDFMột sự thật ít người biết về loài bò là chúng bị mù màu đỏ-lục, nghĩa là màu đỏ và màu lục trông giống hệt nhau đối với chúng. Điều này khiến việc thiết kế một tác phẩm nghệ thuật hấp dẫn cả bò lẫn người trở nên đặc biệt khó khăn.
Xét một bức tranh hình vuông được mô tả bởi lưới \(N \times N\) ký tự (\(1 \le N \le 100\)), mỗi ký tự là R (đỏ), G (lục) hoặc B (lam). Một bức tranh thú vị nếu có nhiều "vùng" màu có thể phân biệt với nhau. Hai ký tự thuộc cùng một vùng nếu chúng kề cạnh trực tiếp (ở phía đông, tây, bắc hoặc nam) và có màu không thể phân biệt được. Ví dụ, bức tranh
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
có \(4\) vùng (\(2\) vùng đỏ, \(1\) vùng lam và \(1\) vùng lục) khi một người nhìn vào, nhưng chỉ có \(3\) vùng (\(2\) vùng đỏ-lục và \(1\) vùng lam) khi một cô bò nhìn vào.
Cho một bức tranh, hãy tính số vùng trong bức tranh khi được nhìn bởi một người và bởi một cô bò.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên \(N\).
- \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(N\) ký tự, mô tả một hàng của bức tranh.
Ràng buộc
- \(1 \le N \le 100\).
- Mỗi ô chứa một trong ba ký tự
R,G,B.
Dữ liệu ra
In ra hai số nguyên cách nhau bởi dấu cách, lần lượt là số vùng trong bức tranh khi được nhìn bởi một người và bởi một cô bò.
Ví dụ
Ví dụ 1
Input
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
Output
4 3
Nguồn
USACO 2014 March Contest, Bronze — Cow Art
Tác giả: Brian Dean, 2014.
Kỳ thi:
- USACO 2014 - Tháng 3 - Hạng Đồng (1 Tháng ba, 2014)
Bình luận