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

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

지뢰 배치 (작은 입력)

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

요약
R이 3 또는 5이고 C가 3에서 5인 작은 지뢰찾기형 단서 격자가 주어질 때, 단서를 만족하는 모든 배치 가운데 가운데 행이 가질 수 있는 지뢰 수의 최댓값을 구한다.
난이도

보통10점 중 6점

유형
완전 탐색, 백트래킹, 구현, 배열
정답자
아직 제출이 없습니다

문제

MineLayer는 R×CR \times C 격자에서 하는 지뢰 찾기 계열 퍼즐이다. 격자의 각 칸에는 지뢰가 하나 있거나 아예 없다. MineLayer 퍼즐은 숫자로 채워진 격자로 주어지고, 각 숫자는 그 칸에 인접한 모든 칸과 그 칸 자신에 놓인 지뢰의 총 개수를 뜻한다. 따라서 숫자는 0 이상 9 이하다.

퍼즐의 목표는 주어진 숫자와 맞아떨어지는 지뢰 배치를 찾는 것이다.

아래는 3행 4열 격자의 예다. 왼쪽이 원래 지뢰 배치이고, 오른쪽이 퍼즐로 주어지는 숫자 격자다.

숫자 격자 하나에 맞는 배치가 여러 개일 수 있으므로, 가운데 행에 놓일 수 있는 지뢰의 최대 개수를 구한다. 행의 개수는 항상 홀수이므로 가운데 행은 위에서 (R+1)/2(R+1)/2번째 행이다. 모든 퍼즐에는 해가 적어도 하나 있다.

입력

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

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

제한

  • 1≤N≤501 \le N \le 50
  • 모든 퍼즐에는 해가 적어도 하나 있다.
  • R=3R = 3 또는 R=5R = 5
  • 3≤C≤53 \le C \le 5

출력

각 테스트 케이스마다 한 줄에 "Case #X: Y"를 출력한다. XX는 1부터 시작하는 테스트 케이스 번호이고, YY는 주어진 숫자 격자를 만족하는 배치 가운데 가운데 행의 지뢰 개수가 가장 많은 경우의 그 개수다.

예제1

  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