다이아몬드 2

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

......#............................
..#.######......................... 
.##########..........###........... 
..#.#########......#######......... 
......#............#######......... 
....................####.#......... 
.......................##..........

위 그림과 같이, #. 만으로 구성된 크기의 격자가 주어집니다. 여기에, # 만으로 아래와 같은 모양이 구성될 경우 이것을 다이아몬드라고 부릅니다.

.........#...........
........###..........
.......#####.........
......#######........ 
.......#####......... 
........###.......... 
.........#...........

격자에서 찾아낼 수 있는 모든 다이아몬드의 개수를 게산하는 프로그램을 작성하세요. 한 # 가 두 개 이상의 다이아몬드에 포함될 경우에도 각 경우를 모두 세어야 합니다.

이 문제에서는 짝수 크기를 갖는 다이아몬드는 없습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄엔 격자의 줄 수 N (1 <= N <= 400) 이 주어집니다. 그 후 줄에 각각 M 길이의 # 와 . 로 구성된 문자열이 주어집니다. (1 <= M <= 400)

출력

각 테스트 케이스마다 한 줄에 찾을 수 있는 다이아몬드의 개수를 출력합니다.

예제 입력

2
5
#####
.###.
..#..
.....
.....
7
......#............................ 
..#.######......................... 
.##########..........###........... 
..#.#########......#######......... 
......#............#######......... 
....................####.#......... 
.......................##.......... 

예제 출력

10
70

노트

4개의 댓글이 있습니다.