다이아몬드 2
문제 정보
문제
......#............................
..#.######.........................
.##########..........###...........
..#.#########......#######.........
......#............#######.........
....................####.#.........
.......................##..........
위 그림과 같이, #
와 .
만으로 구성된 크기의 격자가 주어집니다. 여기에, # 만으로 아래와 같은 모양이 구성될 경우 이것을 다이아몬드라고 부릅니다.
.........#...........
........###..........
.......#####.........
......#######........
.......#####.........
........###..........
.........#...........
격자에서 찾아낼 수 있는 모든 다이아몬드의 개수를 게산하는 프로그램을 작성하세요. 한 #
가 두 개 이상의 다이아몬드에 포함될 경우에도 각 경우를 모두 세어야 합니다.
이 문제에서는 짝수 크기를 갖는 다이아몬드는 없습니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄엔 격자의 줄 수 N (1 <= N <= 400) 이 주어집니다. 그 후 줄에 각각 M 길이의 # 와 . 로 구성된 문자열이 주어집니다. (1 <= M <= 400)
출력
각 테스트 케이스마다 한 줄에 찾을 수 있는 다이아몬드의 개수를 출력합니다.
예제 입력
2 5 ##### .###. ..#.. ..... ..... 7 ......#............................ ..#.######......................... .##########..........###........... ..#.#########......#######......... ......#............#######......... ....................####.#......... .......................##..........
예제 출력
10 70
노트