USACO 2014 - Cow Art

Xem PDF



Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1000 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Mộ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

\(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.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: