A little known fact about cows is that they are red-green colorblind, meaning that red and green look identical to them.

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". 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.

Line 1: The integer N.

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

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

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > March > Bronze