아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

지뢰 배치 (라지)

시간 제한5초메모리 제한512 MB

요약
지뢰찾기식으로 각 칸의 주변 지뢰 수가 주어질 때, 모든 수를 만족하는 배치 중 가운데 행이 가질 수 있는 지뢰 개수의 최댓값을 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

지뢰 배치는 지뢰 찾기와 비슷한 퍼즐이다. 판은 R×CR \times C 격자이고, 각 칸에는 지뢰가 한 개 있거나 아예 없다.

퍼즐은 숫자로 채워진 격자로 주어진다. 각 숫자는 그 칸 자신과 그 칸에 여덟 방향으로 이웃한 칸에 놓인 지뢰를 모두 센 값이다. 판 밖은 세지 않으므로 숫자는 0부터 9까지다.

목표는 주어진 숫자와 하나도 어긋나지 않는 지뢰 배치를 찾는 것이다.

아래 그림은 3×43 \times 4 격자의 예다. 왼쪽이 원래 지뢰 배치이고, 오른쪽이 그 배치에서 만들어진 퍼즐이다.

배치가 여러 가지일 수 있으므로, 가운데 줄에 놓일 수 있는 지뢰 개수의 최댓값을 출력한다. 행의 개수 RR는 항상 홀수여서 가운데 줄은 위에서 (R+1)/2(R+1)/2번째 줄이고, 숫자에 맞는 배치는 항상 하나 이상 있다.

입력

첫째 줄에 테스트 케이스의 개수 NN이 주어진다. 이어서 NN개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에 행의 개수 RR와 열의 개수 CC가 공백으로 구분되어 주어진다. RR는 항상 홀수다. 다음 RR개의 줄에는 각 행의 숫자가 CC개씩 공백으로 구분되어 주어진다.

제한

  • 1≤N≤501 \le N \le 50
  • 모든 퍼즐에는 숫자에 맞는 배치가 적어도 하나 있다.
  • RR는 3 이상 49 이하의 홀수다.
  • 3≤C≤493 \le C \le 49

출력

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. XX는 1부터 시작하는 테스트 케이스 번호이고, YY는 주어진 숫자에 모두 맞는 배치에서 가운데 줄에 놓일 수 있는 지뢰 개수의 최댓값이다.

예제2

  1. 예제 1

    입력
    2
3 3
2 2 1
3 4 3
2 3 2
3 4
1 2 1 1
2 3 3 2
2 2 2 1
    예상 출력
    Case #1: 1
Case #2: 1

  2. 예제 2

    입력
    2
3 5
2 3 3 3 2
4 5 5 4 3
3 3 3 2 2
5 4
1 2 2 2
2 3 3 2
2 3 4 3
2 3 3 2
1 2 2 2
    예상 출력
    Case #1: 2
Case #2: 1