24515번 - 히히 못가

문제

$N \times N$ 격자 모양의 땅에서 로미오는 가장 왼쪽 위 칸, 줄리엣은 가장 오른쪽 아래 칸에 살고 있다. 로미오는 매일 줄리엣을 만나러 가는데, 상하좌우로 인접한 칸으로 이동할 수 있고 땅 밖으로는 나갈 수 없다.

주변을 어슬렁거리던 솔로 부대 상원이는 로미오와 줄리엣의 만남이 마음에 들지 않는다. 수많은 솔로들의 후원으로 돈이 많은 상원이는 로미오와 줄리엣이 만날 수 없도록 주변 땅을 사버리기로 했다.

땅은 몇 개의 영역으로 구분되어있고 이 영역 단위로만 땅을 살 수 있다. 각 영역의 구분을 위해 격자 칸마다 알파벳 대문자를 적어 놓았는데, 상하좌우로 인접한 두 칸의 알파벳이 같다는 것은 같은 영역에 속한 땅이라는 뜻이다. 어떤 두 칸의 알파벳이 같더라도 연결되어 있지 않다면, 다른 영역에 속할 수 있다.

로미오가 줄리엣을 만나는 것을 막기 위해 상원이가 최소 몇 칸의 땅을 사야 하는지 구해보자.

입력

첫 번째 줄에 $N$이 주어진다. $(2 \le N \le 1,000円)$

두 번째 줄부터 $N$개의 줄에 땅의 정보를 나타내는 알파벳 대문자 $N$개가 주어진다. 단, 로미오와 줄리엣의 위치는 .으로 주어진다.

출력

상원이가 최소 몇 칸의 땅을 사야 하는지 출력한다.

제한

힌트