Matrice

시간 제한1초메모리 제한512 MB

요약
정사각형을 대각선 하나로 잘라 만든 삼각형 영역 중 모든 칸의 문자가 같은 것의 개수를 센다.
난이도

보통10점 중 6점

유형
동적 계획법, 행렬, 구현
정답자
아직 제출이 없습니다

문제

요원 Sue Thomas와 그녀의 아들은 격자에서 트리니티를 찾고 있다. 트리니티는 격자의 칸으로 이루어진 특정한 삼각형 모양(어근 “tri”가 암시하듯)을 가리키는 신조어다.

각 트리니티는 격자의 정사각형 영역을 잡고, 그 영역의 두 대각선 중 하나를 기준으로 위쪽 또는 아래쪽에 있는 모든 칸을 제거한 결과다. 대각선은 주대각선(남동-북서 방향) 또는 주반대각선(남서-북동 방향) 중 하나다. 유효한 트리니티는 격자 칸을 적어도 세 개 포함하며, 모든 칸에 같은 문자가 들어 있다.

입력

첫째 줄에 격자의 행 수와 열 수를 나타내는 두 수 N과 M이 주어진다. (1 ≤ N, M ≤ 1000) 다음 N개 줄에 각각 M개의 문자가 주어지며, 각 문자의 ASCII 코드는 33 이상 126 이하다.

출력

입력 격자에 있는 서로 다른 유효한 트리니티의 개수를 출력한다.

예제4

  1. 예제 1

    입력
    2 2
AA
Ad
    예상 출력
    1

  2. 예제 2

    입력
    5 5
#####
####.
###..
##...
#....
    예상 출력
    60

  3. 예제 3

    입력
    5 4
hwwr
eahe
lroy
lswo
oaau
    예상 출력
    0

  4. 예제 4

    입력
    5 6
#girls
##areb
#.#est
#..#!!
#####!
    예상 출력
    7