레이팅 미적용기술에 밝기로 유명한 농부 존은, 들판의 사진을 찍어 소의 위치를 자동으로 찾아낸다는 새 자동 드론 탑재 소 위치 탐지 카메라를 시험하고 있다. 안타깝게도 이 카메라에는 소를 찾는 좋은 알고리즘이 들어 있지 않아서, FJ는 더 나은 알고리즘을 개발하는 데 당신의 도움이 필요하다.
카메라가 촬영한 농장의 항공 사진은 \(N \times N\) 격자의 문자들로 표현되며, 각 문자는 \(A \ldots Z\) 범위로 26가지 색 중 하나를 나타낸다. 농부 존은 잠재적 소 위치(potential cow location, PCL)를 다음과 같이 정의하는 것이 최선이라고 생각한다. PCL은 변이 이미지의 변과 평행한 직사각형 부분 격자(전체 이미지일 수도 있다)로서, 다른 어떤 PCL에도 포함되지 않는다(따라서 PCL의 더 작은 부분집합은 PCL이 아니다). 나아가 PCL은 다음 성질을 만족해야 한다. 직사각형 내부의 내용만 보고 이미지의 나머지를 무시할 때, 정확히 두 가지 색이 존재해야 하며, 한 색은 하나의 연결된 영역을 이루고 다른 색은 둘 이상의 연결된 영역을 이루어야 한다.
예를 들어 내용이 다음과 같은 직사각형은
AAAAA
ABABA
AAABB
A들이 하나의 연결된 영역을 이루고 B들이 둘 이상의 연결된 영역을 이루므로 PCL이 된다. 이는 색 A의 소에 색 B의 점이 있는 것으로 해석된다.
영역 안의 한 칸에서 다른 칸으로 상, 하, 좌, 우로 이동하는 것을 반복하여 영역 전체를 다닐 수 있으면 그 영역은 "연결"되어 있다.
FJ의 카메라가 반환한 이미지가 주어질 때, PCL의 개수를 세시오.
문제 출처: Brian Dean
문제 출처: Brian Dean
입력의 첫째 줄에 격자의 크기 \(N\)이 주어진다 (\(1 \leq N \leq 20\)). 다음 \(N\)개의 줄은 이미지를 나타내며, 각각 \(N\)개의 문자로 이루어진다.
이미지에 있는 PCL의 개수를 출력한다.
where.in · 출력을 쓸 파일 where.out4
ABBC
BBBC
AABB
ABBC2In this example, the two PCLs are the rectangles with contents
ABB
BBB
AAB
ABB
and
BC
BC
BB
BC
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > US Open > Silver