문제2777--바이러스

2777: 바이러스

실행시간 제한: 3 Sec  메모리사용 제한: 512 MB
제출: 3  통과: 2
[제출] [채점기록] [묻고답하기]

문제 설명

N x N 격자판이 있다. 이 격자판의 한 칸은 비어있거나 바이러스가 있거나 벽이 있다. 바이러스는 매 시간 상, 하, 좌, 우 인접한 비어있는 칸으로 증식한다. 바이러스는 인접한 네 개의 칸이 모두 비어있지 않다면, 증식을 멈춘다. 당신은 벽과 바이러스가 배치되어 있는 격자판의 상태가 주어질 때, 정확히 3개의 비어있는 칸을 골라 벽을 설치 해야한다. 벽을 설치 한 후 바이러스가 증식하기 시작하고 모든 증식이 멈추었을 때 비어있는 칸의 갯수를 T라고 할때, 가장 큰 T는 얼마인가.

입력 설명

가장 첫 줄에는 테스트 케이스의 갯수가 주어진다.

각 테스트 케이스는 첫 줄에 격자판의 크기 N 이 주어지고 다음 N 개의 행에 N 개의 정수가 주어진다.

0은 비어있는 칸을 1은 벽을 2는 바이러스를 의미한다.

 

테스트 케이스는 최대 100개 이고 격자판의 크기는 최대 10이다.

격자판 상의 바이러스는 항상 2개이다.

출력 설명

각 테스트 케이스마다 문제에 대한 답을 한줄에 하나의 정수로 출력한다.

입력 예시 Copy

3
3
0 2 2
0 0 0
0 0 0
7
0 0 0 0 0 0 0
0 1 0 2 0 0 1
0 1 1 1 0 0 0
0 0 2 0 0 0 1
0 0 0 1 1 0 1
0 0 0 0 0 0 0
0 1 0 0 0 0 0
5
1 0 0 1 2
1 1 0 0 2
0 1 1 1 0
0 1 0 1 0
1 1 1 1 1

출력 예시 Copy

4
12
6

도움

첫 번째 케이스의 경우

1 2 2

0 1 1

0 0 0

와 같이 벽을 설치해 4개의 빈칸을 얻을 수 있고 이 경우가 가장 많은 빈칸을 만드는 경우이다.

출처/분류