페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3889

Cow Art 1000초 128MB

문제

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


입력

* Line 1: The integer N.

* Lines 2..1+N: Each line contains a string with N characters, describing one row of a painting.


출력

* Line 1: Two space-separated integers, telling the number of regions in the painting when viewed by a human and by a cow.


예제1

입력
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
출력
43

출처

USACO 2014 March Bronze

역링크 공식 문제집만