[2019 SCPC 2차 예선]
폭격
적의 공장들을 파괴하기 위해 폭격을 계획하고 있다.
적국은 \(M\)행 \(N\)열의 격자칸으로 생각한다.
각 칸에는 공장이 있거나 없을 수 있다. 폭탄 하나는 3행 3열에 있는 공장을 모두 파괴할 수 있다.
아래 그림에서 적국은 6행 11열의 격자칸이며 4개의 공장이 있다. 2개의 폭탄으로 모든 공장을 파괴한 모습을 볼 수 있다.
적국의 공장 배치를 입력으로 받아 가능한 최소 개수의 폭탄으로 공장을 모두 파괴하는 방법을 출력하는 프로그램을 작성하라.
이 문제는 주최측이 계산한 답에 대한 비례로 점수가 주어진다. 아래 채점 방식을 확인하라.
- 제한시간: 전체 테스트 케이스는 30개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있습니다.
단, 사용한 출력 함수에 따라서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 될 수 있습니다.
부분 점수를 제대로 받기 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 각 테스트 케이스를 처리한 후에 “fflush(stdout);”을 한번씩 호출하십시오.
Java에서는 "BufferedWriter"를 사용하시오.
(*** 이 문제에서는 “setbuf()”나 “System.out.printIn”을 사용하지 마시오. ***)
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB - 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. \((1 \le T \le 30)\)
각 테스트 케이스의 첫 줄에는 격자칸의 행수 \(M\)과 격자칸의 열 수 \(N\)이 주어진다. \((3 \le M \le 50, 3 \le N \le 500)\)다음 \(M\)개의 줄에 길이 \(N\)인 0/1로 이루어진 문자열이 주어진다. 글자 하나가 격자칸에 공장이 있는지의 여부를 나타낸다. 0이면 공장이 없고, 1이면 공장이 있다는 뜻이다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 250점)
각 테스트 케이스에 대해 250점으로 주최측이 계산한 답과 비교하여 산정된 점수를 테스트케이스 모두에 대해 산술평균한 값으로 정한다. 전체 평균이 250점을 넘는 경우 최종 점수는 250점으로 결정된다.
ㆍ참가자가 제출한 해에서 파괴되지 않는 공장이 있으면 0점이다.
ㆍ그 이외의 경우, 주최측이 계산한 폭탄의 개수가 \(A\), 제출된 폭탄의 개수가 \(B\)일때, 아래 식에 따라 점수가 정해진다.
- \(B \lt 1.2A\)인 경우: \(250(6-5 {B \over A})\)점
- \(B \ge 1.2A\)인 경우: 0점
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
다음 폭탄의 개수 \(P\) 를 출력한다. 그 다음 \(P\)개의 줄에 각 폭탄의 위치를, 파괴되는 범위의 제일 왼쪽 위 격자칸의 행번호 \(R\), 열번호 \(L\)의 쌍으로 출력한다.
(\(P \le (N-2)(M-2),\ 1 \le R \le M-2,\ 1 \le L \le N-2\) 즉, 제일 왼쪽 위 격자칸의 행번호는 1이고 열번호는 1이다.) 폭탄의 위치를 출력하는 순서는 상관이 없다.
입출력예
| 입력 |
|---|
| 1 6 11 00000000000 00000000000 00000100000 00100010000 00000000000 00001000000 |
| 출력 |
|---|
| Case #1 2 4 3 3 5 |