12946번 - 육각 보드

문제

크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다.

육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 어떤 칸을 색칠해야 하는지에 대한 정보가 주어진다.

i번째 줄의 j번째 문자는 (i, j)칸의 정보를 나타내고, '-'인 경우는 색칠하지 않는 것이고 'X'면 색칠해야 하는 것이다.

출력

첫째 줄에 필요한 색의 종류의 최솟값을 출력한다.

제한

힌트