원목 절단

존은 가구 공방을 운영하며, 부유한 고객들은 종종 값비싼 원목으로 만든 가구 세트를 주문한다. 한 무더기의 주문을 처리하려고 존은 가로·세로가 m × n 피트인 직사각형 원목 판 하나를 여러 조각으로 잘라야 한다. 그는 이미 판 위에 잘라낼 각 조각의 윤곽을 그려 두었고, 원형 톱으로 자르려고 한다.

원형 톱에는 한 가지 제약이 있다. 톱은 판의 가장자리(또는 어떤 조각을 떼어낸 뒤 새로 드러난 가장자리)에서 시작하여 직선으로 나아가는 곧은 절단만 할 수 있다. 절단선은 어떤 조각의 내부도 지날 수 없다. 한 조각을 떼어낸 뒤에는 그 조각을 치우고 새로 드러난 가장자리에서 다시 절단을 시작할 수 있으며, 떼어낸 조각들은 원하는 대로 재배치할 수 있다.

그래도 어떤 조각들은 원형 톱만으로는 분리할 수 없다. 예를 들어 두 조각이 서로 맞물려 있거나, 한 조각이 다른 조각 안으로 파고들어 그 조각을 떼어내는 데 필요한 마지막 변을 목재 내부에서만 접근할 수 있는 경우가 있다. 이런 조각들은 나중에 실톱으로 마무리해야 한다. 실톱 작업을 최소화하기 위해 존은 원형 톱으로 판을 가능한 한 많은 부분으로 나누고자 한다. 그 최대 부분 개수를 구하여라.

첫째 줄에 두 정수 m과 n이 주어진다 (1 ≤ m, n ≤ 20). 각각 판의 세로(높이)와 가로(너비)를 피트 단위로 나타낸다.

다음 m개의 줄에는 각각 n개의 문자가 주어지며 판의 표시를 나타낸다. 모든 단위 정사각형은 알파벳 문자 또는 숫자로 표시된다. 같은 조각에 속하는 단위 정사각형은 같은 문자로 표시되고, 각 조각의 정사각형들은 하나의 변으로 이어진(상하좌우로 연결된) 영역을 이룬다. 대문자와 소문자는 서로 다른 것으로 구분한다.

원형 톱만으로 존이 판을 나눌 수 있는 부분의 최대 개수를 정수 하나로 출력한다.

아래 판에서 조각 C와 D는 서로 분리할 수 없고, 조각 E와 Z도 서로 분리할 수 없다.