7207 : 격자 폭탄 배치
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자판 각 칸에 파괴 가능한 내구도가 주어집니다. K개의 폭탄을 적절히 배치하여 파괴할 수 있는 격자 칸 수의 최댓값을 구하십시오. (폭탄의 영향 범위는 자신 칸과 상하좌우 인접 칸이며, 내구도가 1씩 감소하여 0 이하가 되면 파괴됩니다.)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 격자 크기 N, M과 폭탄 개수 K가 주어집니다. (1 ≤ N, M ≤ 5, 1 ≤ K ≤ 3)
둘째 줄부터 N개의 줄에 격자의 내구도 정보가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 격자의 내구도 정보가 공백으로 구분되어 주어집니다.
출력 설명
파괴할 수 있는 격자 칸 수의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 1
1 2 1
2 1 2
1 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
각 위치에 폭탄 1개를 배치할 때, 가운데 변(예: (0,1))에 폭탄을 놓으면 자신(내구도2→1), 좌우상하 중 내구도1인 3개 칸이 0 이하가 되어 최대 3칸을 파괴할 수 있습니다. 폭탄은 서로 다른 위치에 배치해야 합니다.