시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB173918559.441%

문제

$N^2$개의 칸으로 이루어져 있는 $N \times N$ 크기의 정사각형 판이 있다. 이 판의 각 칸은 검은색(B) 또는 흰색(W)으로 칠해져 있다.

이 판에서 연속한 행과 연속한 열을 선택하여 얻을 수 있는 직사각형 모양의 판들 중, 상하좌우로 인접한 두 칸이 서로 다른 색을 가지는 직사각형을 체크무늬 직사각형이라고 한다.

만들 수 있는 체크무늬 직사각형의 개수를 구하여라.

입력

첫째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 2000$)

다음 $N$개의 줄에 걸쳐, 보드의 각 행을 나타내는 길이 $N$의 문자열이 주어진다. 문자열의 각 문자는 B 또는 W 중 하나이다.

출력

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

서브태스크

번호배점제한
110

입력으로 들어오는 판은 체크무늬 직사각형이다

210

$N \leq 10$

320

$N \leq 400$

460

추가 제한 없음

예제 입력 1

2
WB
BW

예제 출력 1

9

예제 입력 2

3
WWW
BWB
WBW

예제 출력 2

25

출처

Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 F번

채점 및 기타 정보

  • 예제는 채점하지 않는다.