7189 : 연구소
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
연구소 지도가 주어집니다. 지도에는 빈칸(0), 벽(1), 바이러스(2)가 있습니다. 벽 3개를 새로 세운 뒤 바이러스가 퍼질 수 없는 안전 영역 크기의 최댓값을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어집니다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보가 공백으로 구분되어 주어집니다.
출력 설명
벽 3개를 세웠을 때 안전 영역 크기의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
27도움
벽 3개를 적절히 배치하여 바이러스 확산을 차단하면 안전 영역의 크기는 최대 27칸이 됩니다.