USACO 2014 March Contest, Bronze
Problem 3. Cow Art
Contest has ended.
Log in to allow submissions in analysis mode
Problem 3: Cow Art [Brian Dean, 2014]
A little known fact about cows is the fact that they are red-green
colorblind, meaning that red and green look identical to them. This makes
it especially difficult to design artwork that is appealing to cows as well
as humans.
Consider a square painting that is described by an N x N grid of characters
(1 <= N <= 100), each one either R (red), G (green), or B (blue). A
painting is interesting if it has many colored "regions" that can
be distinguished from each-other. Two characters belong to the same
region if they are directly adjacent (east, west, north, or south), and
if they are indistinguishable in color. For example, the painting
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
has 4 regions (2 red, 1 blue, and 1 green) if viewed by a human, but only 3
regions (2 red-green, 1 blue) if viewed by a cow.
Given a painting as input, please help compute the number of regions in the
painting when viewed by a human and by a cow.
PROBLEM NAME: cowart
INPUT FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Each line contains a string with N characters,
describing one row of a painting.
SAMPLE INPUT (file cowart.in):
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
OUTPUT FORMAT:
* Line 1: Two space-separated integers, telling the number of regions
in the painting when viewed by a human and by a cow.
SAMPLE OUTPUT (file cowart.out):
4 3
Contest has ended. No further submissions allowed.