지뢰찾기
시간 제한1초메모리 제한128 MB
테두리 칸에 숫자가 적힌 N x N 보드에서 내부 칸에 지뢰를 배치해 모든 숫자 조건을 만족시키면서 지뢰 수를 최대화하는 문제입니다.
문제
N x N 보드가 주어진다. 가장자리 칸에는 지뢰가 없으며, 각 가장자리 칸에는 숫자가 적혀 있다. 이 숫자는 그 칸과 8방향으로 인접한 칸들 중 지뢰가 있는 칸의 개수를 나타낸다.
가장자리를 제외한 모든 칸은 #으로 표시되어 있으며, 이 칸들 중 일부에 지뢰를 놓을 수 있다. 모든 가장자리 숫자가 인접한 지뢰의 개수와 일치하도록 지뢰를 놓을 때, 보드에 놓을 수 있는 지뢰의 최대 개수를 구하시오.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 보드의 크기 N이 주어진다. 다음 N개의 줄에는 보드를 나타내는 길이 N의 문자열이 하나씩 주어진다. N은 1 이상 100 이하이다.
출력
각 테스트 케이스마다 보드에 놓을 수 있는 지뢰의 최대 개수를 한 줄에 하나씩 출력한다.