문제 보기 - 빨간 직사각형 (kriii3_QQ)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
1000 ms 512 MiB 38 9 23.68%

N × M 크기의 격자판이 있다. 격자판의 각 칸은 빨간색 또는 파란색으로 색칠되어 있다. 편의상 ij열 (1 ≤ i ≤ N, 1 ≤ j ≤ M)의 격자를 (i, j)로 표시한다.

주어진 격자판 내에서 빨간색 격자로만 이루어진 직사각형의 개수를 세는 프로그램을 작성하자. 여기서 직사각형은 1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M를 만족하는 네 개의 정수 x1, y1, x2, y2에 의해 결정되며, x1 ≤ x ≤ x2y1 ≤ y ≤ y2를 만족하는 모든 격자 (x, y)를 일컫는다. 예를 들어 x1 = 2, y1 = 3, x2 = 4, y2 = 4라면, 6개의 격자 (2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4)가 모두 한 직사각형에 속한다. 두 직사각형이 서로 다르다는 것은 [x1, y1, x2, y2]이 서로 다르다는 것이다.

입력

첫 번째 줄에 행의 수 N (1 ≤ N ≤ 3,000)과 열의 수 M (1 ≤ M ≤ 3,000)이 공백을 사이로 두고 주어진다.

다음 N개의 줄의 각 줄에는 M개의 문자가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄은 주어진 격자판의 i번째 행의 격자에 칠해진 색들을 나타내며, 이 중 j번째 문자는 (i, j)에 칠해진 색을 나타낸다. 모든 문자는 'R' 또는 'B'로만 구성된다. 'R'은 해당 칸이 빨간색임을, 'B'는 해당 칸이 파란색임을 의미한다.

출력

첫 번째 줄에 빨간색 격자로만 이루어진 직사각형의 개수를 출력한다.

부분문제

부분문제 점수 N, M
1 10 ≤ 500
2 10 ≤ 3,000

입출력 예제

입력 예시 출력 예시
2 2
RR
RB
5

5개의 직사각형은 다음과 같다. ([x1, y1, x2, y2]으로 나타냄)

  • [1, 1, 1, 1]
  • [1, 1, 1, 2]
  • [1, 2, 1, 2]
  • [1, 1, 2, 1]
  • [2, 1, 2, 1]