돌로 가두기
시간 제한5초메모리 제한512 MB
최대 20칸인 N행 M열 격자에서 돌을 가장 적게 놓아 K개 이상 지점을 경계에서 끊어지게 둘러쌉니다.
문제
가로선 개와 세로선 개로 이루어진 격자가 있다. 가로선과 세로선이 만나는 교차점은 모두 개이고, 각 교차점에는 돌을 하나까지 놓을 수 있다.
교차점 하나가 다음 두 조건 중 하나를 만족하면 그 점은 갇힌 점이다.
- 그 점에 돌이 놓여 있다.
- 그 점에서 출발해 격자선을 따라 이동할 때, 빈 교차점만 지나서는 격자 경계의 빈 교차점에 도달할 수 없다.
이동은 격자선을 따라 이웃한 교차점으로 한 칸씩만 한다. 출발점, 지나는 점, 도착점이 모두 비어 있어야 그 경로를 쓸 수 있다. 따라서 경계 위에 있는 빈 교차점은 갇힌 점이 아니다.
갇힌 점이 개 이상이 되도록 돌을 놓으려고 한다. 필요한 돌의 최소 개수를 구하라.
예를 들어 격자에서 점 8개를 가두려면 돌이 적어도 6개 필요하다. 아래 그림은 그런 배치 중 하나이고, 갇힌 점을 x로 표시했다.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다. 이어지는 개의 줄에 각각 세 정수 , , 가 공백으로 구분되어 주어진다.
제한
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 필요한 돌의 최소 개수이다.