만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

치노의 라떼 아트 (Easy)

면접 대비

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

요약
격자에 채워진 크림이 N×N 정사각형에서 모서리 하나의 M×M 정사각형을 뺀 하트 모양인지 판별합니다.
난이도

쉬움10점 중 3점

유형
구현, 완전 탐색, 행렬
정답자
아직 제출이 없습니다

문제

치노는 하트 모양의 라떼 아트를 만드는 연습을 하고 있다. 치노가 연습하며 남긴 흔적을 우연히 본 코코아는 그중 하트 모양의 라떼 아트가 몇 개인지 궁금해졌다. 코코아를 위해 라떼 위 크림이 하트 모양인지 판별하는 프로그램을 만들어 보자.

하트 모양

이 문제에서 치노의 라떼 아트는 단위 정사각형으로 나뉜 2차원 격자로 주어진다. #는 크림으로 꽉 찬 정사각형, .는 크림이 없는 정사각형을 나타낸다.

두 양의 정수 NN과 MM(0<M<N0<M<N)이 존재해서, N×NN\times N 정사각형의 네 구석 중 한 곳에서 M×MM\times M 정사각형을 제거한 모양을 하트 모양으로 정의한다.

다음은 N=5N=5, M=2M=2인 경우의 하트 예시이다.

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

위 정의에 해당하는 모양의 크림이 라떼 위에 정확히 하나만 놓여 있는 경우에만 하트로 인정한다. 크림 안에 구멍이 뚫려 있거나, 떨어진 크림 덩어리가 여러 개인 경우(각 덩어리가 하트 모양인 경우도 포함)는 하트 모양으로 보지 않는다.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤1001\le T\le 100)

다음 줄부터 TT개의 테스트 케이스가 아래 형식으로 주어진다.

각 테스트 케이스의 첫 줄에 격자의 세로 길이 RR과 가로 길이 CC가 공백으로 구분되어 주어진다. (2≤R,C≤102\le R, C\le 10)

이어서 RR개의 줄에 격자의 ii행을 나타내는 길이 CC의 문자열이 주어진다. 각 문자열은 # 또는 .로만 이루어진다.

출력

각 테스트 케이스에 대해, 주어진 라떼 아트가 하트 모양이면 1, 아니면 0을 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    3
    5 5
    ###..
    ###..
    #####
    #####
    #####
    10 10
    ...#.#....
    ..#.#.#...
    ..#.#.#...
    ..#####...
    .#.....#..
    .#.#.#.#..
    .#..#..#..
    .#.###.#..
    .#.....#..
    ..#####...
    4 8
    ........
    .##.....
    .#......
    ........
    
    예상 출력
    1
    0
    1