18번 - 체크무늬 찾기

$N^2$개의 칸으로 이루어져 있는 $N \times N$ 크기의 정사각형 판이 있다. 이 판의 각 칸은 검은색(B) 또는 흰색(W)으로 칠해져 있다. 이 판에서 연속한 행과 연속한 열을 선택하여 얻을 수 있는 직사각형 모양의 판들 중, 상하좌우로 인접한 두 칸이 서로 다른 색을 가지는 직사각형을 체크무늬 직사각형이라고 한다. 만들 수 있는 체크무늬 직사각형의 개수를 구하여라.

첫째 줄에 정수 $N$($1 \leq N \leq 2000$)이 주어진다. 다음 $N$개의 줄에 걸쳐, 보드의 각 행을 나타내는 길이 $N$의 문자열이 주어진다. 각 문자는 'B' 또는 'W' 중 하나이다.

만들 수 있는 체크무늬 직사각형의 개수를 출력한다.

서브태스크 1 (10점): 입력으로 들어오는 판은 체크무늬 직사각형이다 서브태스크 2 (10점): $N \leq 10$ 서브태스크 3 (20점): $N \leq 400$ 서브태스크 4 (60점): 추가 제한 없음