시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 274 | 105 | 73 | 34.434% |
N x N 보드에 테러범들이 지뢰를 설치해 놓았다. 다행히도 가장자리 칸에는 지뢰가 없는 것으로 확인되어 지뢰 탐지기를 설치했다. 지뢰 탐지기는 주변에 몇 개의 지뢰가 있는지를 보여준다. 즉, 가장자리 칸의 숫자는 인접한 칸에 있는 지뢰의 개수를 나타낸다.
111000 2####0 3####1 3####1 2####1 112110
위 그림은 6 x 6 보드를 나타낸다. 이 보드에는 최대 10개의 지뢰가 놓일 수 있다.
111000 2*###0 3***#1 3****1 2*#*#1 112110
주어진 보드에 놓일 수 있는 최대 지뢰 개수를 출력하는 프로그램을 작성하시오.
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 보드의 크기 N(1 ≤ N ≤ 100)이 주어지고 두 번째 줄부터는 보드를 나타내는 N개의 문자열이 주어진다. 각 문자열의 길이는 N이다.
각 테스트 케이스에 대해서 보드에 놓일 수 있는 최대 지뢰의 개수를 한 줄에 하나씩 출력한다.
3 6 111000 2####0 3####1 3####1 2####1 112110 5 11100 2###1 3###1 2###1 12210 7 1233210 1#####1 1#####1 1#####2 2#####2 2#####2 1232211
10 6 20